目录
一、前言
二、正题
1、暴力解法；
2、贪心算法：
3、图解贪心
一、前言
什么是贪心算法？
“贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。”
贪心的本质是从局部最优取到全局最优的过程
就好比我们要我从三国中挑选十个武将陪我征战四方
那我们每次挑选肯定是想条武力最猛的一个 从而达到全局的最猛的十个人
其次我想说，经过这两天贪心算法的刷题，总结出来ta其实没有固定的套路 就是不断尝试从局部最优到全局最优的过程 而且贪心算法的尝试往往嵌套一些技巧（比如数组边界的限制）
所以唯一的难点就是如何通过局部最优，推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？
不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
如何验证可不可以用贪心算法呢？
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
贪心算法一般分为如下四步：
将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解
二、正题
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]输出: 3解释:从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。因此，3 可为起始索引。
1、暴力解法；
暴力的方法很明显就是O(n^2)的，遍历每一个加油站为起点的情况，模拟一圈。
如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。
暴力的方法思路比较简单，但代码写起来也不是很容易，关键是要模拟跑一圈的过程。
for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！
public int canCompleteCircuit(int[] gas, int[] cost) { for (int i=0;i<gas.length;i++){ int rest=gas[i]-cost[i];//从i开始油箱第一次剩余的油量 int index=(i+1)%gas.length;//车子的下标，i位置我们已经走过了 while (rest>0&&index!=i){//只有油箱的剩余油量大于0 才可以继续往下走 rest+=gas[i]-cost[i];//得到的减去消耗的就是剩余的 index=(index+1)%gas.length; } if (rest>=0&&index==i) return i;//如果走完一圈发现可以走下来，就返回以当前起点为初始点 } //如果所有的下标都走完了都没找到这个起点 return -1; }2、贪心算法：
可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。（题解来源：代码随想录）
那么为什么一旦[i，j] 区间和为负数，起始位置就可以是j+1呢，j+1后面就不会出现更大的负数？
如果出现更大的负数，就是更新j，那么起始位置又变成新的j+1了。
而且j之前出现了多少负数，j后面就会出现多少正数，因为耗油总和是大于零的（前提我们已经确定了一定可以跑完全程）。
那么局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。
代码如下：
public int canCompleteCircuit(int[] gas, int[] cost) { int start=0;//开始点 int totalSum=0;//总的油箱剩余油量 int curSum=0;//维持正数的油箱 for (int i=0;i<gas.length;i++){ totalSum+=gas[i]-cost[i]; curSum+=gas[i]-cost[i]; if (curSum<0){ curSum=0; start=(i+1)%gas.length;//i之前肯定都回不到起点 } } if (totalSum<0){//如果总的油箱是负数，说明不论从哪里出发都回不到起点 return -1; } return start; }3、图解贪心
以该题为例：gas = [1,2,3,4,5]cost = [3,4,5,1,2]下图的黑色折线图即总油量剩余值，若要满足题目的要求：跑完全程再回到起点，总油量剩余值的任意部分都需要在X轴以上，且跑到终点时：总剩余汽油量 >= 0。
为了让黑色折线图任意部分都在 X 轴以上，我们需要向上移动黑色折线图，直到所有点都在X轴或X轴以上。此时，处在X轴的点即为出发点。即黑色折线图的最低值的位置：index = 3。
这个图是从0点（i=0,即第一个站）出发的折线图，那么改变出发点时，这个图会怎么变化呢？你可以自己去画一画，你会发现，整体折线图的形状是没有变的，改变的是y值，相当于将折线图在Y轴方向上上下平移。那么，当最小点落在X轴上时（也就是使得最小点y=0时），整体折线在X轴上方，y值恒大于等于0，也就是剩余油量一直不为负，可以绕行一圈。对于本例，也就是使得i=3时，y=0。此时，意味着从i=3，第四个站出发，到此站时即没有加油也没有耗油，剩余油量为0。
代码如下：
public int canCompleteCircuit(int[] gas, int[] cost) { int min=Integer.MAX_VALUE;//为了记录油箱最低时的时刻 int minIndex=0;//记录油箱最低时的下标 int totalSum=0;//油箱的油量 for (int i=0;i<gas.length;i++){ totalSum+=gas[i]-cost[i]; if (totalSum<min){ min=totalSum;//记录最低油箱的时候 minIndex=i;//记录最低点的下标 } } if (totalSum<0){//说明无论从哪一点出发，都无法到达终点！ return -1; } return (minIndex+1)%gas.length; }这道题其实对初入贪心的同学来说还是有点难度的 但它确实是一道很巧妙的贪心题目。最后送给大家一句话，也是这道题的核心。
如果结局是好的,痛苦积累最多的那天过后,生活会开始好起来的,纵使再遇苦难,总有美好的事可以抵消苦难.