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

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;
    }

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