Day31｜贪心算法part01：理论基础、455.分发饼干、376. 摆动序列、53. 最大子序和

理论基础

记得贪心没有规律即可！解不出来就看题解。

455. 分发饼干

先把学生和饼干都排序（Arrays.sort只能升序），然后都从后往前遍历，把最大的饼干给需求最大的孩子（贪心）

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int end = s.length - 1;
        int count = 0;
        for (int i = g.length - 1; i >= 0; i--) {
            if(end >= 0 && g[i] <= s[end]){
                count++;
                end--;
            }
        }
        return count;
    }
}

376. 摆动序列

把数组按照山峰这样的表示，可以看到最长的就是删除不是峰顶或峰底的元素后的元素大小。

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];
            //如果当前差值和上一个差值为一正一负
            //等于0的情况表示初始时的preDiff
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
}

• 考虑三种特殊情况：

  • 上下坡中有平坡

- #### 情况二：数组首尾两端

- #### 情况三：单调坡度有平坡

53. 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            if(sum < 0){
                sum = 0;
            }
            sum += nums[i];
            maxSum = maxSum = Integer.max(sum , maxSum);

        }
        return maxSum;
    }

}

//贪心：先累加，当前和为负数时放弃，统计最大。