LeetCode 134 Gas Station

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

概述

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 站的净耗油量。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/