力扣134-加油站（java题解）

题目链接：134. 加油站 - 力扣（LeetCode）

前情提要：

因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。

贪心方法：局部最优推出全局最优。

如果一个题你觉得可以用局部最优推出全局最优，并且没有反例来反驳的话就可以用贪心来试试。

题目思路：

该题入手，你可能知道，当总容量减去总消耗量大于等于0，那么该路程一定是可以环路行驶一周的，但是怎么确认出发的加油站编号呢？

我们用贪心的思路来想想。

将每个加油站的净增量（gas[i] - cost[i]）算出，其实就是从该加油站出发到下一站所得到的油。

我们将每一个加油站的净增量累加，如果该和小与0，说明到该加油站的油量已经不足了，那么只有从下一站才可能为出发点。

举个例子。

在这里插入图片描述

从0到4我们开始累加，我们加到2时发现，我们剩余的油量已经不支持我们到达2了，那0和1就不可能是出发点，我们的出发点只会3后面。

因为不管是从0还是1开始到2的油量都为负数了，所以肯定是不可能从0和1出发的。

那i+1后面就不会出现更大的负数？

如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。

那么局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

最终代码：

class Solution {//如果该路线的总消耗量减去总增长量为0 那么一定是可以走完全程的 现在我们就是要确认出发点//本题首先我们要把到每个加油站油的净增量 res[i] = gas[i] - cost[i]给算出来 并累加起来 //如果我们从0到i连续累加小与0 说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。//也就是我们这个连续和的区间不可能行驶一圈了 因为我们的剩油量小于0 不能到达下一个加油站//此时我们只有从下一个加油站开始出发才可能会走完一圈//所以我们的局部最优就是：当前累加的和只要小与0 就会从下一个加油站开始重新出发 //全局最优 找到可以走完一圈的路线public int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;//totalSum就是所有加油站加起来的净增量，如果小与0 那么不可能会走完一圈int totalSum = 0;int nextIndex = 0;for(int i = 0;i < gas.length;i++){curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];//当curSum<0时 那前面的 0 到 i都不可能是起始位置 只有后面的才有可能为起始位置//也就是我们在实时更新我们出发的位置 直到可以走完一圈//其实我们的起始位置肯定是前面的连续和为负数 后面的都大于0if(curSum < 0){//在这里我们更新出发点，此时前面加油站所累加的油就要清空nextIndex = i + 1;curSum = 0;}}if(totalSum < 0)return -1;return nextIndex;}
}