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