参考

代码随想录

题目一：LeetCode 122.买卖股票的最佳时机II

按照自己的想法，无非就是在最低点买入，在最高点卖出，因此只需要找到成对的极小值和极大值，就可以计算利润了。代码实现如下：

class Solution {
public:int maxProfit(vector& prices) {int index = 0;int profit = 0;bool flag1,flag2;int value1,value2;vector> vec;while(index < prices.size()){flag1 = flag2 = false;//求极小值value1 = prices[index];for(;index < prices.size(); index++){if(prices[index] <= value1) value1 = prices[index]; //这里要包含等号else{ //下一个值比当前极小值大，说明已经找到了极小值flag1 = true;break;}}//求极大值value2 = value1;for(;index < prices.size(); index++){if(prices[index] >= value2){ //这里要包含等号value2 = prices[index]; if(index == prices.size()-1) //右边界处理   flag2 = true;   }else{flag2 = true;break;}}//保存极值if(flag1 && flag2) vec.push_back(pair(value1,value2));else break;  //找不到一组极值，退出 }for(int i = 0; i < vec.size(); i++)profit = profit - vec[i].first + vec[i].second;return profit;      }
};  

上面的求解过程只关注了极小值和极大值两个点，但其实利润是可以分解的，从极小值到极大值的过程中，每天都是正利润，例如求prices[4]-prices[1]，完全可以分解为(prices[4]-prices[3]) + (prices[3]-prices[2]) + (prices[2]-prices[1])，这样只需要关注当天相对于前一天的利润。按照分解利润的思想，不再需要求极值点，而只需要关注当前相对于前一天的利润，而且我们只需要关注正利润，这就是贪心所贪的地方。代码实现如下：

class Solution {
public:int maxProfit(vector& prices) {int profit = 0;for(int i = 1; i < prices.size(); i++)profit += max(prices[i]-prices[i-1],0);return profit;}
};

题目二：LeetCode 55. 跳跃游戏

因为这个题问的是能不能跳到最后一个位置，因此只需要做判断就可以了，不必关心具体的路径。每个位置给出了能跳的最大长度，将每个位置的最大长度转化成一个范围，最终判断这个范围能不能覆盖最后一个位置就可以了。

如上图所示，左图能覆盖终点，而右图不能覆盖终点。

但其实不必列出所有位置的覆盖范围，只需要每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。如下图所示：

在代码实现上，i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。

而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。

如果cover大于等于了终点下标，直接return true就可以了。

代码实现如下：

class Solution {
public:bool canJump(vector& nums) {int cover = 0;for(int i = 0; i <= cover; i++){cover = max(i+nums[i],cover);if(cover >= nums.size()-1) return true;}return false;}
};

题目三：LeetCode 45. 跳跃游戏II

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。
整体最优：一步尽可能多走，从而达到最小步数。

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

这里有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

• 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
• 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

class Solution {
public:int jump(vector& nums) {int curDistance = 0, nextDistance = 0;int step = 0;for(int i = 0; i < nums.size(); i++){nextDistance = max(i+nums[i],nextDistance);if(i == curDistance){if(curDistance != nums.size()-1){step++;curDistance = nextDistance;if(nextDistance >= nums.size()-1)   break;}else break;}}return step;}
};