算法训练（leetcode）二刷第二十三天 | 455. 分发饼干、*376. 摆动序列、53. 最大子数组和

455. 分发饼干

leetcode题目地址

贪心算法。将两个数组排序后都从大向小匹配（优先考虑胃口）。

两个数组哪个是外层移动，哪个是内层移动：胃口在外，饼干尺寸在内。

也就是说：

• 若当前胃口若对得上当前饼干尺寸，则二者同时移动，且结果数+1；
• 若当前饼干尺寸无法满足当前胃口，就需要胃口数组向更小的方向移动，而饼干尺寸不变。

**Tips：**若是从小到大匹配（优先考虑饼干），则内外层交换。

时间复杂度： $O(nlogn)$ 排序用时O(nlogn) 匹配用时O(n)
空间复杂度： $O(1)$

// java
class Solution {


    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int cnt = 0;
        int i=s.length-1;
        for(int j=g.length-1; j>=0&&i>=0; j--){
            if(s[i] >= g[j]){
                cnt++;
                i--; 
            }
        }

       
        return cnt;
    }
}

*376. 摆动序列

leetcode题目地址

题目要求严格摆动序列，因此前一组差和后一组差必须一正一负。而起始状态下没有计算差值默认前一组差值为0。因此在判断时: (preDiff >= 0 || preDiff <= 0)加入了等于0的判断。

**Tips：**为什么这里用preDiff=0判断起始状态而不是用curDiff=0判断？

因为curDiff计算的是当前一组的差值，若当前组差值为0则为平坡，不进入if；而preDiff是在if中进行更新的，因此只会在初始状态下问为0，其余情况均不为0。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// java
class Solution {

    public int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1) return nums.length;
        int preDiff = 0;
        int curDiff = 0;
        int result = 1;

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

53. 最大子数组和

leetcode题目地址

求最大连续子数组和，对数组中元素依次求和，当和为负值时将其置为0重新累加。为处理数组中全为负的情况，需要先记录最大值再置0。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// java
class Solution {
    public int maxSubArray(int[] nums) {
        int maxVal = -10001;
        int curVal = 0;
        for(int i=0; i<nums.length; i++){
            curVal += nums[i];
            
            if(curVal > maxVal) maxVal = curVal;
            if(curVal<0) curVal = 0;
        }
        return maxVal;
    }
}