LeetCode #134：Gas Station(加油站)

题目描述

本题最直观的方法是暴力枚举每个加油站为起点的情况、每个点绕一圈，那么时间复杂度为 O(n²)，会超时。此时我们需要用贪心的思想来优化它。

我们首先判断各个加油站的总油量是否大于等于总代价。若满足，则说明肯定能在某结点处绕一圈回到原点；若不满足，肯定没法绕一圈回到原点。

之后我们开始从下标 0 遍历两个数组，记油箱中当前油量为 curSum、以 0 为汽车出发点开始找答案 (resIndex)，遍历每个元素的同时执行 curSum += gas[i] - cost[i]。一旦 curSum 在第 i 次循环中小于 0（在这一点没油了），说明下标区间 [resIndex, i] 范围内的数都不能作为起点（可用反证法证明，假设存在起点 j ∈ [resIndex, i] 会怎样），此时应将新的起点设为 i + 1，即 resIndex = i + 1，并将油箱油量也置 0（代表从新的起点重新出发）。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int totalSum = 0; // 统计各个加油站的总油量与总代价之差
        int curSum = 0; // 当前油箱油量
        int resIndex = 0; // 结果下标
        for(int i = 0; i < n; i ++) {
            totalSum += gas[i] - cost[i];
            curSum += gas[i] - cost[i];
            if(curSum < 0) { // 在i处没油了，说明下标区间[resIndex, i]范围内的数都不能作为起点，将起点置为i+1
                resIndex = i + 1;
                curSum = 0;
            }
        }

        if(totalSum < 0) // 各个加油站的总油量与总代价之差<0，肯定不行
            return -1;

        return resIndex;
    }
};