Shouyu

Appearance

加油站 ​

题目描述 ​

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

  • 如果题目有解，该答案即为唯一答案。
  • 输入数组均为非空数组，且长度相同。
  • 输入数组中的元素均为非负数。

题目链接：https://leetcode.cn/problems/gas-station/

文章讲解：https://programmercarl.com/0134.加油站.html

思考 ​

要走遍所有加油站，要保证每步的剩余油量是正的。

每个加油站的油量是 rest[i] = gas[i]-cost[i]，再计算一个当前油量 curSum += rest[i]，一旦curSum小于0，那么说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

第一个问题 ​

有没有可能 [0，i] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零呢？ 如图：

img

如果 curSum<0 说明 区间和1 + 区间和2 < 0， 那么 假设从上图中的位置开始计数curSum不会小于0的话，就是 区间和2>0。

区间和1 + 区间和2 < 0 同时 区间和2>0，只能说明区间和1 < 0， 那么就会从假设的箭头初就开始从新选择起始位置了。

第二个问题 ​

为什么首次连续和到达最后一个加油站时的起始加油站是能完成环路的起始加油站？这不是明明没有计算之前的加油站吗？

很有意思，我们首先要计算整个环路的总剩油量通过 totalSum ≥ 0来确保有答案。这时算法一定找到了一个start位置（首次）（因为题目保证答案为1）。

这时环路分为两部分：

  • A部分：从start到数组末尾，累计盈余为正值
  • B部分：从数组开始到start-1

由于totalSum = A部分盈余 + B部分盈余 ≥ 0，而A部分盈余 ≥ 0，所以即使B部分盈余为负，其绝对值也不会超过A部分盈余。

当从start出发：

  1. 先走A部分：油量从0开始，始终≥0，到达数组末尾时油量为A部分盈余
  2. 再走B部分：带着A部分盈余的油量开始，能够覆盖B部分的消耗

贪心的思想体现在第一个问题：

  1. 局部贪心选择：当 currentSum < 0时，算法贪心地选择跳过当前所有不可能的起点，直接将起点设为i+1
  2. 全局最优：通过局部的贪心选择，最终得到全局最优解

代码实现 ​

C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start = 0;
        int curSum = 0;
        int totalSum = 0;
        for(int i = 0;i < gas.size();i++){
            curSum+=gas[i]-cost[i];
            totalSum+=gas[i]-cost[i];
            if(curSum < 0){
                start = i + 1;
                curSum = 0;
            }
        }
        if(totalSum < 0) return -1;
        return start;
    }
};