代码随想录算法训练营第三十一天 | LeetCode 455. 分发饼干、376. 摆动序列、53. 最大子数组和

代码随想录算法训练营第三十一天 | LeetCode 455. 分发饼干、376. 摆动序列、53. 最大子数组和

文章链接：分发饼干        摆动序列        最大子数组和

视频链接：分发饼干        摆动序列        最大子数组和

目录

代码随想录算法训练营第三十一天 | LeetCode 455. 分发饼干、376. 摆动序列、53. 最大子数组和

1. 贪心算法理论基础

1.1 什么是贪心

1.2 什么时候用贪心

1.3 贪心一般解题步骤

2. LeetCode 455. 分发饼干

2.1 思路

2.2 代码

3. LeetCode 376. 摆动序列

3.1 思路

3.2 代码

4. LeetCode 53. 最大子数组和

4.1 思路

4.2 代码

---

1. 贪心算法理论基础

1.1 什么是贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

1.2 什么时候用贪心

说实话贪心算法并没有固定的套路。所以唯一的难点就是如何通过局部最优，推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？也没有！靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

如何验证可不可以用贪心算法呢？最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

1.3 贪心一般解题步骤

1. 将问题分解为若干个子问题
2. 找出适合的贪心策略
3. 求解每一个子问题的最优解
4. 将局部最优解堆叠成全局最优解

做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。

贪心没有套路，说白了就是常识性推导加上举反例。

2. LeetCode 455. 分发饼干

2.1 思路

1. 本题有两个数组，一个数组是饼干，一个数组是胃口，要求尽可能满足多的小孩，因此是大饼干给大胃口，小饼干给小胃口，这样才不至于浪费
2. 局部最优：每次找到一个大的饼干，尽量去喂胃口大的小孩
3. 全局最优：可以喂饱最多的小孩的数量
4. 为什么这里局部最优就可以退出全局最优？找不出反例那就是了！
5. 首先对两个数组排序 Arrays.sort(数组)。定义变量 result 表示喂饱多少个小孩，index 从最后一个位置开始。我们从右往左遍历，用大饼干满足小孩，其实用小饼干满足小孩也是可以的就是从左往右遍历
6. for(int i=g.length-1; i>=0; i++)里面再加个 if(index>=0&&s[index]>=g[i])然后 result++；index--。因为我们遍历饼干的时候只有饼干投喂成功才向前遍历，没有成功投喂，饼干就继续等，等到可以遍历再向前遍历。if 里的条件顺序不能换，不然就数组越界。然后 return result 就行了。
7. 这里就是 for 循环控制小孩的胃口，if 遍历控制饼干。条件顺序颠倒是不可以的。for 循环一定要先遍历胃口。如果 for 循环控制的是饼干，if 遍历控制胃口，我们从右往左遍历，在 if 条件可能就会出现一直卡住的情况，比如 饼干 [1,3,5,9] 胃口 [1,2,7,10]，就会一直卡在胃口 10 那里最终就没人能吃饱

2.2 代码

//
class Solution {
    // 思路1：优先考虑饼干，小饼干先喂饱小胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int start = 0;
        int count = 0;
        for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                start++;
                count++;
            }
        }
        return count;
    }
}

3. LeetCode 376. 摆动序列

3.1 思路

1. 局部最优：单调坡上的元素都删除掉
2. 全局最优：变成了摆动最长的序列。就这样好像找不出明显反例可以反驳，因此可以尝试这样的贪心算法
3. 这里可以不用真的删除这些元素然后再求数组的大小，我们定义 result 遇到摆动就++，遇到坡度就不++，问题是如何判断是摆动呢？
4. 定义 prediff=nums[i]-nums[i-1]，curdiff=nums[i+1]-nums[i]，如果 prediff 和 curdiff 为一正一负就找到了一个峰值，即（prediff<0&&curdiff>0 || prediff>0&&curdiff<0），就 result++
5. 上面的数组的值相邻是不同的因此有坡，如果是相同元素相邻就会出现平坡，因此：

6. 

7. 情况一：上下坡有平坡 ，比如 [1,2,2,2,1]。我们就要把左边或者右边的端点处的值保留，留一边即可，选左边也行右边也行，我们选择保留右边因此条件变为（prediff<=0&&curdiff>0 || prediff>=0&&curdiff<0）

8. 

9. 情况二：首尾元素，只有两个元素比如 [1,2]。而我们算 prediff 和 curdiff 一共需要三个元素，题目说明只有两个不相等元素也算是两个摆动，因此我们默认 prediff=0，并且 result=1，这样就相当于在数组开头加了一个和原数组开头一样的元素，比如上面的就变成了 [1,1,2]，这样就把那个判断条件的规则统一了。但如果是 [2,2] 这种就是一个摆动了，此时也会让其变为 [2,2,2]，但是这个不会触发那个判断条件，result 也就不会++了
10. 如果长度小于等于 1 就直接 return 数组长度即可。定义初始化 prediff=0，curdiff=0，result=1。for(int i=0; i

11. 

12. 情况三：单调坡有平坡，比如 [1,2,2,2,3,4]。这里摆动长度只有 2，就是头和尾，因为摆动的差值必须为 1 正 1 负。但这里如果直接按照上面的运行就会得到摆动长度为 3，问题出在 prediff 直接跟着 curdiff 更新，我们其实只需要在出现坡度变化即摆动的情况再更新 prediff 的值，这样的好处是遇到平坡时不会改变 prediff。
13. 解决方法就是把 prediff=curdiff 放入 if 判断条件语句中，因为判断条件就是是否出现了摆动，而出现摆动我们更新 prediff 的值就对了

3.2 代码

//
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;
    }
}

4. LeetCode 53. 最大子数组和

4.1 思路

1. 题目是给一个数组求最大连续子数组的和，注意是要求连续的。连续和+=nums[i]

2. 局部最优：如果连续和在某个位置后是负数，如果还+=nums[i]只会让nums[i]变小，与其继续要前面的连续和，不如直接让连续和变为0再重新+=nums[i]，重新开始遍历。因此局部最优就是如果求解连续和时连续和为负数，直接抛弃它，因为只会拖累我们的总和

3. 全局最优：在数组中找到了最大连续子数组的和。从这个局部最优好像可以推出全局最优，而且找不到明显的反例反驳这个想法，因此可以试一下这个贪心思路

4. 注意：我们是当连续和为负数时才将连续和置为0重新开始遍历，而不是遇到数组中的一个负数就置为0，因为加了这个负数连续和还可能是负数

5. 定义个result记录最终结果最大值，初始化为Integer.MIN_VALUE。定义个count记录连续和。result就是用count更新为最大的结果

6. for(int i=0; iresult)，result=count就更新为最新的最大值。if(count<0)，就把count=0重新开始遍历。最后return result就行了

4.2 代码

//
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
            if (count <= 0){
                count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
            }
        }
       return sum;
    }
}