理论基础
贪心算法核心：选择每一阶段的局部最优，从而达到全局最优。
455.分发饼干
455. 分发饼干 - 力扣（LeetCode）代码随想录 (programmercarl.com)455. 分发饼干 - 力扣（LeetCode）
贪心算法理论基础！_哔哩哔哩_bilibili
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子
i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j，都有一个尺寸s[j]。如果s[j] >= g[i]，我们可以将这个饼干j分配给孩子i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。示例 1:
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。示例 2:
输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.提示：
1 <= g.length <= 3 * 1040 <= s.length <= 3 * 1041 <= g[i], s[j] <= 231 - 1
局部最优就是把大的饼干尽量喂给大胃口的小孩，这样才不会浪费。
先将饼干和小孩分别排序：
Arrays.sort(s);
Arrays.sort(g);从大饼干对应大胃口小孩开始匹配：
for(int index = g.length - 1; index >= 0; index--){if(start >= 0 && g[index] <= s[start]){start--;count++;}
}综合代码：
class Solution {// 思路2：优先考虑胃口，先喂饱大胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int start = s.length - 1;// 遍历胃口for (int index = g.length - 1; index >= 0; index--) {if(start >= 0 && g[index] <= s[start]) {start--;count++;}}return count;}
}376. 摆动序列
376. 摆动序列 - 力扣（LeetCode）
代码随想录 (programmercarl.com)
贪心算法，寻找摆动有细节！| LeetCode：376.摆动序列_哔哩哔哩_bilibili
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。- 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组
nums，返回nums中作为 摆动序列 的 最长子序列的长度 。示例 1：
输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8] 输出：7 解释：这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9] 输出：2提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000进阶：你能否用
O(n)时间复杂度完成此题?
局部最优：删掉单调坡上的节点，这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长的摆动序列。
按照以上的图可以分析出来，不需要删除元素，重点在于统计数组的峰值数量。
那什么时候需要统计波动呢？有两种情况：
1、prediff(nums[i] - nums[i-1])<0 且 curdiff(nums[i+1] - nums[i])>0
2、prediff(nums[i] - nums[i-1])>0 且 curdiff(nums[i+1] - nums[i])<0
以上情况只适用于i位于非首尾位置的时候。如果i位于首尾，则prediff和curdiff都无法计算，那i位于首尾的时候是什么情况呢？还有平坡的时候是prediff或者curdiff等于0，这时候应该怎么计算呢？
情况一、上下坡中有平坡：
实际摆长为3，要么删除前面3个2，要么删除后面3个2：
删左面三个 2 的规则，那么 当 prediff = 0 && curdiff < 0 也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。
情况二、i位于数组首尾两端：
当i位于首端的时候，假设数组最前面的数字和i所在的首端的位置相同：
针对以上情形，result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）
代码如下：
class Solution {public int wiggleMaxLength(int[] nums) {// 如果数组长度小于等于1，直接返回数组长度if (nums.length <= 1) {return nums.length;}// 当前差值int curDiff = 0;// 上一个差值int preDiff = 0;// 计数，初始为1，因为序列中至少有一个元素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)) {// 计数加1count++;// 更新上一个差值preDiff = curDiff;}}// 返回计数，即摆动子序列的长度return count;}
}
