455. 分发饼干
解题思路：
为了满足更多的小孩，就不要造成饼干尺寸的浪费。
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略，先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
var findContentChildren = function (g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let res = 0;
let count = s.length - 1;
for (let i = g.length - 1; i >= 0; i--) {
if (count >= 0 && s[count] > g[i]) {
res++;
count--;
}
}
return res;
};
376. 摆动序列
解题思路：
如果前后出现峰值，那就说明preDiff和curDiff一正一负，需要考虑三种情况。
- 情况一：上下坡中有平坡
记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)，这里允许 prediff === 0 ，是因为可能存在
[1,2,2,2,1] 的情况，这时的条件就是prediff === 0 - 情况二：数组首尾两端
默认右边有峰值，result初始值为1，只遍历左边。 - 情况三：单调坡中有平坡
针对 [1,2,2,2,3,4] 的情况，答案为2，如果实时更新prediff就会导致多统计一次，这种情况就需要在摆动的时候再更新prediff就不会导致误判。
var wiggleMaxLength = function (nums) {
if (nums.length <= 1) {
return nums.length;
}
let preDiff = 0;
let curDiff = 0;
let result = 1;
for (let i = 0; i < nums.length - 1; i++) {
curDiff = nums[i + 1] - nums[i];
if ((preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)) {
result++;
preDiff = curDiff;
}
}
return result;
};
53. 最大子数组和
解题思路：
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”。
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。
var maxSubArray = function (nums) {
let result = -Infinity;
let count = 0;
for (let i = 0; i < nums.length; i++) {
count += nums[i];
if (result < count) {
result = count;
}
if (count < 0) {
count = 0;
}
}
return result;
};
