理论基础
贪心算法的本质是由局部最优推到全局最优，没有特定的套路
455.分发饼干
455. 分发饼干 - 力扣（LeetCode）
本题考虑将大饼干喂给胃口大的孩子，遍历孩子胃口的数组，用大饼干依次喂，直到满足条件，再移动饼干的位置
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int start = s.length - 1;
//要遍历小孩胃口，不合适就下一个，因为要从大到小把饼干分完
for (int i = g.length - 1; i >= 0; i--) {
//这里用if就可以，不需要用while
if (start >= 0 && s[start] >= g[i]) {
start--;
count++;
}
}
return count;
}
}
376. 摆动序列
376. 摆动序列 - 力扣（LeetCode）
本题局部最优是“删除”单调序列上中间的值，由此可以推出全局最优最长摆动子序列的长度。要注意有平坡的情况，要么都在curDiff加上=，要么在preDiff加上=
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];
if (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
count++;
preDiff = curDiff;
}
}
return count;
}
}
53. 最大子序和
53. 最大子数组和 - 力扣（LeetCode）
本题主要是如何找到子数组的起始位置，当前面数组和为负数并且下一个数为正数时，那么就将起始位置设置为这个正数，然后再持续计算比较子数组总和
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
maxSum = Math.max(sum, maxSum);
//sum小于0时，就重新设置起始位置
if (sum < 0) {
sum = 0;
}
}
return maxSum;
}
}
