贪心的一天，头好晕
理论基础
什么是贪心
每次选择都采取局部最优，最终得到全局最优。
（一定是每个阶段都采取局部最优，能够推出全局最优的，如果得不到全局最优就不用贪心法）
套路
没有套路。
但是可以判断用不用贪心：
通过数学归纳/反证法的方式，模拟一下看看能不能局部最优->整体最优。
（一般情况下就是反证法就行了，看看能不能找到反例，得不到整体最优的）
贪心法的一般过程
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。
做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。
分发饼干
leetcode：455. 分发饼干
贪心法
思路
排序后，遍历每个孩子，找最小能满足胃口的饼干，最后结果就是尽可能多地满足孩子。
复杂度分析
时间复杂度：O(NlogN)。主要花在排序上。
空间复杂度：O(1)。
注意点
- 双指针就够了，不用起两层循环。
代码实现
双指针法（暴力法两层循环太辣眼睛了就不放上来了）
class Solution {
public:
// 胃口和饼干排序
// 遍历孩子，对每个孩子遍历饼干，找可能的最小的饼干
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int count = 0;
// 不用套两个循环，可以双指针
int gIndex = 0;
int sIndex = 0;
while(gIndex != g.size() && sIndex != s.size()){
if(s[sIndex] >= g[gIndex]){ // 能满足 下一个孩子 下一块饼干
count++;
gIndex++;
sIndex++;
}else{ // 满足不了，还是这个孩子，下一块饼干
sIndex++;
}
}
return count;
}
};
摆动序列
leetcode：376. 摆动序列
回溯法
思路
理论上应该是可行的，但是我写不出来，在面对输入[1,2,3,4,5,6,7,8,9]时，不能正确返回[2]。
代码实现
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
public:
// 试下回溯暴力枚举
void backtracking(vector<int>& nums,int begin,int sign){
if(path.size() > 0) result.push_back(path);
for(int i = begin;i < nums.size();i++){
// path元素不足两个时，直接放入元素
if(path.size() <= 1) path.push_back(nums[i]);
else{ // 两个元素及以上时，检查符号是否相反
if( (nums[i] - path.back()) * sign > 0){
path.push_back(nums[i]);
backtracking(nums,i + 1,-sign);
path.pop_back();
}
}
}
}
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() <= 2) return nums.size();
int sign = 0;
if(nums[1] - nums[0] > 0 ) sign = 1;
else if(nums[1] - nums[0] < 0) sign = -1;
backtracking(nums,0,-sign);
int ret = 0;
for(vector<int> vec : result){
if(vec.size() > ret) ret = vec.size();
}
return ret;
}
};
贪心法
思路
出现峰值result++，且规定最右边有一个峰值。
可能的三种情况：
- 上下坡出现峰值 。
preDiff > 0 && postDiff < 0 || preDiff < 0 && postDiff > 0 - 上下坡出现平坡。这种也要算，所以
preDiff >= 0 && postDiff < 0 || preDiff <= 0 && postDiff > 0 - 单调上下出现平坡。这种不能算，
preDiff只在出现峰值时更新即可
综上，条件就是preDiff >= 0 && postDiff < 0 || preDiff <= 0 && postDiff > 0，而且每次只计算postDiff，如果是峰值才更新preDiff。
（本质上来说，就是把坡压缩掉）
复杂度分析
时间复杂度：O(N)。一轮遍历。
空间复杂度：O(1)。
注意点
- nums有0个、1个元素时直接返回大小，但2个及以上就要在循环里了（2个元素时要判断是否是相等的两个元素）。
代码实现
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
int preDiff = 0; // 前差值
int postDiff = 0; // 后差值
int result = 1; // 规定最右边有一个峰值
for(int i = 0;i < nums.size() - 1;i++ ){
postDiff = nums[i+1] - nums[i];
// 如果出现峰值，就result++并更新preDiff
// 这步压缩平坡，只有出现峰值才会进入操作
if( (preDiff >= 0 && postDiff < 0 ) || (preDiff <= 0 && postDiff > 0) ){
result++;
preDiff = postDiff;
}
}
return result;
}
};
最大子数组和
leetcode：53. 最大子数组和
贪心法
思路
局部最优：和为负数时，不论加甚麽都只会拖累整体累和。因此连续和为负数的时候，抛弃当前累和，从下一个元素开始计算累和。
整体最优：得到最大连续子数组的累和。
复杂度分析
时间复杂度：O(N)。遍历一轮。
空间复杂度：O(1)。
注意点
- 求最大和，要在遍历过程中尝试向上更新最大值（最大值可能出现在中间）。
代码实现
class Solution {
public:
// 连续和为负数时，从当前元素开始计数
int maxSubArray(vector<int>& nums) {
int sum = 0;
int maxSum = INT32_MIN;
for(int i = 0;i < nums.size();i++){
sum += nums[i];
maxSum = sum > maxSum ? sum : maxSum;
if(sum < 0){
sum = 0;
}
}
return maxSum;
}
};