Leetcode加油站问题，这个答案该怎么理解?-灵析社区

Leetcode加油站问题，这个答案该怎么理解? [题目地址](https://link.segmentfault.com/?enc=d2mJ1SfcYHYKPiUGgUgePA%3D%3D.2YdtYy%2FcREJeqwiCxmn68EsZvmdfj2AWYI7uCsrsN%2Fwfv9s9R7cno4Mfoh63FZEpjLusm4QqYkA%2BHZPqXs7R2DTfvb4kipoJCw7fglifIz7WkwBlP1BDSnj9iveq456mM4c4MSZ2O0kGN%2F3O94HQcw%3D%3D) 我在官方题解的下方评论中发现了一个答案，但是对于为什么这个答案可行我并不理解。 #### 为什么`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的，从前往后合并就可以了） * `sum =0(每次合并时前缀和都是>=0的，最后一次也还是)，矛盾。故不存在可行解。 #### 为什么起点是` (minIndex + 1 )%gas.length`呢？ [评论区答案](https://link.segmentfault.com/?enc=r%2FN8jvlniz3gY4T95xawig%3D%3D.SF5rSrLJnu%2BZSbG169GnjVXcJZWg9WQENv33uYOQd4F9Q9ZLTSdSU3AA8zDp4a98niPB%2BD0nJQje%2Fx30s0%2BY%2BxyOQV6QlLdBDVVPno3AOOce%2BvvsPLk9f1z1GUbKDkUJ9PFvVg7fWt6c%2BYQlwO539H8SL88hG1pLhS716cLFaISeGN2xcG6tmQXXXg1M0RE3) 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 没有直接前缀和的吗？ **显然如果存在仅一个起点S能走完全程，那么从任意一个点出发绕完一圈，在S处的油量一定是最少的。** > 所以只要验证走完全程的前缀和非负，然后找到前缀和最小的点就是起点了 int canCompleteCircuit(vector& gas, vector& cost) { // 化为边上的净开销 int size = gas.size(); int i; vector 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; } 这里的显然我也没有明白。