LeetCode #134:Gas Station(加油站)

题目描述

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

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

之后我们开始从下标 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;
    }
};

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注