算法 - Leetcode加油站问题，这个答案该怎么理解?

Question

Leetcode加油站问题，这个答案该怎么理解?

题目地址

我在官方题解的下方评论中发现了一个答案，但是对于为什么这个答案可行我并不理解。

为什么sum >= 0说明有解，否则就无解呢？

这个答案我有一些思路。

remainGas[i] = gas[i] - stataion[i]sum = all remainGas[i] i from 0 to n -1

• sum >= 0

  • 将相邻的remainGas[i]，且它们的前缀和(这里的前缀和指的是这几个remainGas构成序列的前缀和)都大于等于0，合并成一个节点（此时这个节点代表了一段路径）。
  • 这样我们就可以得到一个更小的子问题了，而且我们总是可以合并的，因为sum>=0（如果不存在的话，sum应该是<0的。）。
  • 最终只会得到一个节点（此时这个节点代表了一条可行的路径）

任何一种可行解都可以按照上述的方法构造出来。（这个很容易构造，可行解的前缀和都是>=0的，从前往后合并就可以了）

• sum < 0
  假设此时存在一个可行解，那么存在一个上述的构造过程。由构造过程可得，sum应该是>=0(每次合并时前缀和都是>=0的，最后一次也还是)，矛盾。故不存在可行解。

为什么起点是 (minIndex + 1 )%gas.length呢？

评论区答案

class Solution {    public int canCompleteCircuit(int[] gas, int[] cost) {        int sum = 0;        int min = Integer.MAX_VALUE;        int minIndex = -1;        for(int i = 0; i < gas.length; i++){            sum = sum + gas[i] - cost[i];            if(sum < min && sum < 0){                min = sum;                minIndex = i;            }        }        if(sum < 0) return -1;        return (minIndex + 1 )%gas.length;    }} 

我在评论区还看到另一份思路一样的答案，并且他还给出了一些说明。

没有直接前缀和的吗？ 显然如果存在仅一个起点S能走完全程，那么从任意一个点出发绕完一圈，在S处的油量一定是最少的。 所以只要验证走完全程的前缀和非负，然后找到前缀和最小的点就是起点了

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {        // 化为边上的净开销        int size = gas.size();        int i;        vector<int> edge_cost(size);        for (i = 0; i < size; i++) edge_cost[i] = gas[i] - cost[i];        int cs = 0;        for (i = 0; i < size; i++) {            int tmp = edge_cost[i];            edge_cost[i] = cs;            cs += tmp;        }        if (cs < 0)return-1;        int p = 0;        cs = 0;        for (i = 0; i < size; i++) {            if (edge_cost[i] < cs) {                cs = edge_cost[i];                p = i;            }        }        return p;    }

这里的显然我也没有明白。

Answer 1

为什么起点是 (minIndex + 1 )%gas.length呢？

remainGas[0] ... remainGas[i] ... remainGas[n-1]

假设i为起点位置，那么sum remainGas[i...j](j = i, (i+1)%n .. (i+n-1)%n) > 0(必须保证任意的前缀都>0才可以走到下一站)，所以
sum remainGas[0..i-1] < sum remainGas[0...j] (j = i, ..., n-1)。

假设存在z，距离i最近且使得sum remainGas[0...z] < sum remainGas[0..i-1]，那么
sum remainGas[z...j](j = z, .. i-1) > 0，此时从以z+1为起始点，我们走到i是可行的，又因为i为起始点，所以以z+1为起点可以走完一圈。此时就存在了两个解，与题目中说的存在唯一解矛盾，故不存在这样的z。

故sum remmainGas[0...i-1]为min(sum remaiGas[0..j]) (j = 0,1,...n-1)