贪心算法

贪心算法基础

贪心算法的特点

• 每一步都做出当前最优选择
• 不回溯
• 局部最优导致全局最优

适用场景

• 问题具有贪心选择性质
• 问题具有最优子结构

经典题目

分发饼干（LeetCode 455）

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);

    int i = 0, j = 0;
    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) {
            i++;
        }
        j++;
    }
    return i;
}

买卖股票的最佳时机II（LeetCode 122）

public int maxProfit(int[] prices) {
    int profit = 0;

    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}

跳跃游戏（LeetCode 55）

public boolean canJump(int[] nums) {
    int maxReach = 0;

    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

跳跃游戏II（LeetCode 45）

public int jump(int[] nums) {
    int jumps = 0;
    int currentEnd = 0;
    int farthest = 0;

    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);

        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}

无重叠区间（LeetCode 435）

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;

    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

    int count = 0;
    int end = intervals[0][1];

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < end) {
            count++;
        } else {
            end = intervals[i][1];
        }
    }
    return count;
}

划分字母区间（LeetCode 763）

public List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) {
        last[s.charAt(i) - 'a'] = i;
    }

    List<Integer> result = new ArrayList<>();
    int start = 0, end = 0;

    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);

        if (i == end) {
            result.add(end - start + 1);
            start = i + 1;
        }
    }
    return result;
}

练习题

1. 柠檬水找零（LeetCode 860）
2. 用最少数量的箭引爆气球（LeetCode 452）
3. 根据身高重建队列（LeetCode 406）
4. 分发糖果（LeetCode 135）
5. 加油站（LeetCode 134）