上面承接贪心算法整理
-
十张钞票让拿五次，那指定每一次只拿最大的
-
如果能局部最优推出整体最优而且还想不到反例那就试试贪心。
-
有时候不知道自己用了贪心，因为本就应该那么做
1、分发饼干
先排序然后遍历
2、摆动序列
.删除序列中的一些数，使的相邻两个数的差值为正负交替。
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。 两个连续的递增或递减的一定要删掉，那么在这一段就是局部最优的
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
大体逻辑有了，但初始值不好弄，每次都是与前面比较的，但是刚开始没有pre的值。针对这个修改代码的逻辑，如下图所示，pre是0，但是也是上升的，所以判断时不能只是要求一个正一个负，pre可以为0
“仅有一个元素或者含两个不等元素的序列也视作摆动序列。”仅有一个元素也视为摆动序列长度为1，两个不等的元素的摆动序列长度为2。
那么刚开始时要加上1。但是问题来了，如果刚开始加上这个1，是不是可以认为第一个数与前面构成了摆动，那么第二个数怎么办。因此将这个1理解成最右边的摆动，将加1的逻辑算到最终的时候
3、最大子序和
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
下面这个过程就是代码的过程
4、买卖股票的最佳时机II
给一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
必须在再次购买前出售掉之前的股票
计算你所能获取的最大利润
问题在于如果想要买，只能前一天为未持有股票状态，那么使用贪心如果保证操作的连续性。
如果确定是持有还是卖出，那么和上面一个题一样，比较每天的利润，看利润的差值
计算连续和，但这里是下一个是负数就不加了
下一个是负数就卖出，不影响下下一次的买入，所以这里的贪心就是把所有的正数都加起来
不需要担心考虑卖出操作的影响
第一天没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天！
收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
result += max(prices[i] - prices[i - 1], 0);
}
return result;
}
};
5、跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
if (nums.size() == 1) return true; // 只有一个元素，就是能达到
for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
cover = max(i + nums[i], cover);
if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
}
return false;
}
};
6、跳跃游戏II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
这个代码不大理解
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() == 1) return 0;
int curDistance = 0; // 当前覆盖最远距离下标
int ans = 0; // 记录走的最大步数
int nextDistance = 0; // 下一步覆盖最远距离下标
for (int i = 0; i < nums.size(); i++) {
nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖最远距离下标
if (i == curDistance) { // 遇到当前覆盖最远距离下标
if (curDistance != nums.size() - 1) { // 如果当前覆盖最远距离下标不是终点
ans++; // 需要走下一步
curDistance = nextDistance; // 更新当前覆盖最远距离下标（相当于加油了）
if (nextDistance >= nums.size() - 1) break; // 下一步的覆盖范围已经可以达到终点，结束循环
}
else break; // 当前覆盖最远距离下标是集合终点，不用做ans++操作了，直接结束
}
}
return ans;
}
};
7、K次取反后最大化的数组和
给个数组和数字k，要求必须翻转k次数组，这样修改后，返回数组可能的最大值。
按照绝对值排序，然后从大值开始捋，遇到负数将其翻转并k–一次，如果捋完以后k还大于0，那么在最小值上反复的翻转将k消耗完。
加油站
加油站，每个加油站有gas[i]油，到下一个加油站需要耗费cost[i]的油,问从哪个下标开始能环形一周，如果不能返回-1
