LeetCode 134 Gas Station

    
        标签：
        
            贪心法
        
            LeetCode
        
    发布于：2022-02-21 21:33:05
    编辑于：2022-02-22 09:35:38
    浏览量：900

概述

https://leetcode.com/problems/gas-station/

暴力遍历

很显然这道题可以直接暴力遍历，O(n^2) 时间复杂度。

贪心法

https://labuladong.gitee.io/algo/3/27/108/

我们从任意点出发，可以画出以下油量曲线：

显然当某点降到 0 以下时车辆将抛锚。

我们换用任意其他点做为起始点，该曲线的形状是不会变的，只是会上下位移。（其实并不是不会变，只有当油量刚好用完时才这样，此时起始油量和结束油量一致，但是没关系，我们可以假装最后一段路用掉了所有剩余油量，不影响结论。）

显然，我们应当选择曲线的最低处做为起始点。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int val = 0;
        int minVal = INT_MAX, minIdx = 0;
        for (int i = 0; i < gas.size(); i ++) {
            val += gas[i] - cost[i];
            if (val < minVal) {
                minVal = val;
                minIdx = i + 1;
            }
        }
        if (val < 0) return -1;
        return minIdx == gas.size() ? 0 : minIdx;
    }
};

另外要注意的一点是，minIdx = i + 1;，这是因为 cost[i] 是从第 i 站到 i + 1 站的损耗，所以 gas[i] - cost[i] 是到第 i + 1 站的净耗油量。

Links: leetcode-134-gas-station