122.买卖股票的最佳时机 II
最开始的思路是为了获得最大利益，低买高卖，在所有的低点都尝试购买，碰到更低的点，就把之前的抛掉，从新购买低点，然后我们要将所有挣钱的时候值都加起来。
将数组的值转成柱状图或则折线图来看，我们想要的就是所有的上升部分的值，所以在遍历时判断当前元素是否比前一个大，大则可以更新在这个点时上升的线段的最大值。在碰到下降的线段，即当前值比上一个值小的时候，说明前面的上升线段结束了，将收益累加起来，从新开始找上升的线段。由于只能持有一只股票，但可能会碰到连续的低点，采取的策略时当天买当天卖，这样碰到更低的点时，计算之前的低点的收益就是0，然后再在低点买入。
由于这个策略的收益累加的过程是在由高点转低点的时候进行的，所以，如果在最后的计算的过程中是连续上涨的，这样就不会收割这段上升曲线。因此，加了 flag 辅助判断是否是这个情况，是的话，把最后这段上升曲线的值累加上。
class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size() <= 1) return 0;int min_price = prices[0];int max_price = INT_MIN;int profit = 0;int maxprofit = 0;int flag = 0;for(int i = 1; i < prices.size(); i++){if(prices[i] > prices[i-1]){max_price = prices[i];flag = 0;}else{if(i != 1) profit = max_price - min_price;maxprofit += profit;min_price = prices[i];max_price = prices[i];flag = 1;}}if(flag == 0) {profit= max_price - min_price;maxprofit += profit;}return maxprofit;}
};卡哥这边的思路更巧妙。
本题首先要清楚两点：
- 只有一只股票！
- 当前只有买股票或者卖股票的操作
想获得利润至少要两天为一个交易单元。
在这个前提下，其实最终利润是可以分解的。
假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，这段的收益就是每天的收益的累加，而不是第 0 天买到第 3 天卖的两点操作！
所以我们要关注的点从找每一个高低点，转换成了，计算每两天的买卖的差额，并收集所有的为正的收益。
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;}
};55. 跳跃游戏
这题简单说就是一开始我们知道能走一段距离，我们在已知的能走到的区域中，每走一步能知道当前点能到的距离，我们要做的是寻找还能走到的最远的距离，然后更新我们已知的最远距离，再在这个距离里找下一个能跳到的最远的距离。当我们已知的最远距离能大于终点时，说明能到达终点。
class Solution {
public:bool canJump(vector<int>& nums) {int cover = 0;if (nums.size() == 1) return true; // 只有一个元素，就是能达到for (int i = 0; i <= cover; i++) { // 注意这里是小于等于covercover = max(i + nums[i], cover);if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了}return false;}
};题解中看到更直接的方法，就不管3721，硬往前走。每次走一格都能知道在该位置能到达的最远距离，我们一直往前走，我们只需要维护一个当前能走到的最远距离，即知道我们最远能到哪，每走一步就更新我们已知的最远距离。当我们走到了已知的最远的地方，但前面还有路时，我们已经不能往前走了，所有到达不了终点。如果这条路走完了，那么说明我们到达了终点。
class Solution {
public:bool canJump(vector<int>& nums) {int m_max = 0;for(int i = 0; i< nums.size(); i++){if(m_max < i) return false; m_max = max(m_max, i + nums[i]);}return true;}
};45.跳跃游戏 II
这题在做了前一题之后，就好想很多。
题目已知肯定能走到终点，走到每个格子我们能知道目前能到达的最远距离，那么在已知的距离中，找下次能到的最远的距离，每次都选择走到已知的最远距离，这样是最快能到终点的。这里贪的是走到已知的最远距离，不是该格子能到的最远距离。所以处理起来是一段一段的，每走一个格子就在已知的能走的距离里，找下次最远能到哪，然后直接走到最远。
int jump(vector<int> &nums)
{int ans = 0;int start = 0;int end = 1;while (end < nums.size()){int maxPos = 0;for (int i = start; i < end; i++){// 能跳到最远的距离maxPos = max(maxPos, i + nums[i]);}start = end; // 下一次起跳点范围开始的格子end = maxPos + 1; // 下一次起跳点范围结束的格子ans++; // 跳跃次数}return ans;
}
从上面代码观察发现，在已知的距离中寻找下一个最远的距离，其实就是 i++ 的过程，是一只往后走的，这个两层循环，i 是从头跑到尾的。所以可以改写成一个 for 循环。
关于步数的计算，每次寻找完后可以看作是直接走到了已知的最远，知道了新的能到的最远，可以直接到达新的最远，这里步数+1，然后在新到达的最远的距离的格子又得知了一段新的最远，接着再在这段新的已知距离中找下一个最远再直接跳。
class Solution {
public:int jump(vector<int>& nums){int ans = 0;int end = 0;int maxPos = 0;for (int i = 0; i < nums.size() - 1; i++){maxPos = max(nums[i] + i, maxPos);if (i == end){end = maxPos;ans++;}}return ans;}
};