算法训练营day26--455.分发饼干+376. 摆动序列+53. 最大子序和

一、455.分发饼干

题目链接：https://leetcode.cn/problems/assign-cookies/
文章讲解：https://www.programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html
视频讲解：https://www.bilibili.com/video/BV1MM411b7cq

1.1 初见思路

小饼干先喂饱小胃口

1.2 具体实现

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int num = 0;
        for(int i=0;i<s.length;i++){
            int curCookie = s[i];
            if(num==g.length){
                break;
            }
            if(curCookie>=g[num]){
                num++;
            }
        }
        return num;
    }
}

1.3 重难点

二、 376. 摆动序列

题目链接：https://leetcode.cn/problems/wiggle-subsequence/
文章讲解：https://www.programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html
视频讲解：https://www.bilibili.com/video/BV17M411b7NS

2.1 初见思路

需要考虑多种情况：上下坡中有平坡、数组首尾两端、单调坡度有平坡

2.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;
    }
}

2.3 重难点

三、53. 最大子序和

题目链接：https://leetcode.cn/problems/maximum-subarray/
文章讲解：https://www.programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
视频讲解：https://www.bilibili.com/video/BV1aY4y1Z7ya

3.1 初见思路

如果包含正数，肯定需要从正数开头
要考虑数组中只有负数的情况

3.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;
    }
}