从几个贪心算法的问题体会如何通过问题等价来简化问题
算法学习的路线，个人体验，首先是学习基本的数据结构和算法，通晓每种数据结构适合存储什么类型的信息，然后了解通用的算法思想，比如贪心，双指针，单调栈，回溯等。第三步就是学会抽象，或者说等价，将具体的问题等价为简单的问题，然后用通用的算法去解决。第四步，就是有的算法只存在理论上的可行性，实际由于各种原因，如何去工程上的近似，或者有些问题不存在理论上的解法，只存在工程上的解法。
基本的数据结构，其实就是栈，队列，数组，链表，哈希，树，图之类的，其他的复杂数据结构都是再基本数据结构基础上组合出来的，比如跳表。
这次我们就从几个贪心算法体验问题等价能够带来的问题简化。
跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
1 | 示例 1: |
刚看到本题一开始可能想：当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？
其实跳几步无所谓，关键在于可跳的覆盖范围！
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
这个范围内，别管是怎么跳的，反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
局部最优推出全局最优，找不出反例，试试贪心！
买卖股票的最佳时机II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
1 | 示例 1: |
这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入…循环反复。
如果想到其实最终利润是可以分解的，那么本题就很容易了！
如何分解呢？
假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！
那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1])…(prices[1] - prices[0])。
其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。
那么只收集正利润就是贪心所贪的地方！
局部最优：收集每天的正利润，全局最优：求得最大利润。
加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
示例 1: 输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
直接从全局进行贪心选择，情况如下：
情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。