理论基础

贪心算法的本质是由局部最优推到全局最优，没有特定的套路

455.分发饼干

455. 分发饼干 - 力扣（LeetCode）
本题考虑将大饼干喂给胃口大的孩子，遍历孩子胃口的数组，用大饼干依次喂，直到满足条件，再移动饼干的位置

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;
        //要遍历小孩胃口，不合适就下一个，因为要从大到小把饼干分完
        for (int i = g.length - 1; i >= 0; i--) {
            //这里用if就可以，不需要用while
            if (start >= 0 && s[start] >= g[i]) {
                start--;
                count++;
            }
        }
        return count;
    }
}

376. 摆动序列

376. 摆动序列 - 力扣（LeetCode）
本题局部最优是“删除”单调序列上中间的值，由此可以推出全局最优最长摆动子序列的长度。要注意有平坡的情况，要么都在curDiff加上=，要么在preDiff加上=

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        int curDiff = 0;
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            curDiff = nums[i] - nums[i - 1];
            if (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
}

53. 最大子序和

53. 最大子数组和 - 力扣（LeetCode）
本题主要是如何找到子数组的起始位置，当前面数组和为负数并且下一个数为正数时，那么就将起始位置设置为这个正数，然后再持续计算比较子数组总和

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            maxSum = Math.max(sum, maxSum);
            //sum小于0时，就重新设置起始位置
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxSum;
    }
}