LeetCode-加油站

 最近刷题的时候遇到一个有意思的解法，解决思路不同常法，且拥有不错的性能表现。下面是分析过程：

以该题为例：
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
下图的黑色折线图即总油量剩余值，若要满足题目的要求：跑完全程再回到起点，总油量剩余值的任意部分都需要在X轴以上，且跑到终点时：总剩余汽油量 >= 0。

为了让黑色折线图任意部分都在 X 轴以上，我们需要向上移动黑色折线图，直到所有点都在X轴或X轴以上。此时，处在X轴的点即为出发点。即黑色折线图的最低值的位置：index = 3。

柱状图
绿色：可添加的汽油 gas[i]
橙色：消耗的汽油 cose[i]

折线图：
虚线（蓝色）：当前加油站的可用值
实线（黑色）：从0开始的总剩余汽油量

执行用时： 0 ms, 在所有 java 提交中击败了 100.00% 的用户
内存消耗： 37.2 MB, 在所有 java 提交中击败了 72.07% 的用户

 1 public int canCompleteCircuit(int[] gas, int[] cost) {
 2     int len = gas.length;
 3     int spare = 0;
 4     int minSpare = Integer.MAX_VALUE;
 5     int minIndex = 0;
 6 
 7     for (int i = 0; i < len; i++) {
 8         spare += gas[i] - cost[i];
 9         if (spare < minSpare) {
10             minSpare = spare;
11             minIndex = i;
12         }
13     }
14 
15     return spare < 0 ? -1 : (minIndex + 1) % len;
16 }

使用语言：java

时间复杂度：O(N)
空间复杂度：O(1)

需要补充说明的是，许多人认为

index=3，从第三个点出发，gas[ 2 ] = 3, cost [ 2 ] = 5，显然错误

实际上是误解了图中各点的含义，尤其是索引号的含义。首先整张图是从0点（i=0,即第一个站）出发的到达各个点时剩余油量图，X轴对应的是到达的各个点。i=0对应的是第一个站，即gas[0]这个站，刚到时即没有加油也没有耗油，为0；i=1对应的是第二个站，即gas[1]这个站，刚到时，经历了0+gas[0]-cost[0]，此时剩余的油量为-2；实际上

index=3，对应的是第四个站，也就是从第四个站出发，gas[ 3 ] = 4, cost [ 3 ] = 1，起步成功

这个图是从0点（i=0,即第一个站）出发的折线图，那么改变出发点时，这个图会怎么变化呢？实际去画，会发现整体折线图的形状是没有变的，改变的是y值，相当于将折线图在Y轴方向上上下平移。那么，当最小点落在X轴上时（也就是使得最小点y=0时），整体折线在X轴上方，y值恒大于等于0，也就是剩余油量一直不为负，可以绕行一圈。对于本例，也就是使得i=3时，y=0。此时，意味着从i=3，第四个站出发，到此站时即没有加油也没有耗油，剩余油量为0。

正常解题思路往往是用贪心算法，然后优化贪心算法减少遍历的次数以提高性能，而这个解法剑出奇招，思路很是新鲜。