【练习】【贪心】力扣134. 加油站

题目

134. 加油站

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

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

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

输出: 3

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]

输出: -1

来源：力扣134. 加油站

思路（注意事项）

先判断油量和路程各自总和的差值，如果油量>=路程，则一定可以找到解。

纯代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sum_gas = 0, sum_cost = 0, start = 0, n = gas.size(), sum = 0;

        for (int i = 0; i < n; i ++)
        {
            sum_gas += gas[i];
            sum_cost += cost[i];
        }
        if (sum_gas < sum_cost) return -1;

        for (int i = 0; i < n; i ++)
        {
            sum += gas[i] - cost[i];
            if (sum < 0)
            {
                start = i + 1;
                sum = 0;
            }
        }
        return start;
    }
};

题解（加注释）

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // sum_gas 表示所有加油站的油量总和
        // sum_cost 表示所有加油站的消耗总和
        int sum_gas = 0, sum_cost = 0;
        // start 表示可能的起点
        int start = 0;
        // n 表示加油站的数量
        int n = gas.size();
        // sum 表示当前油量的累加值
        int sum = 0;

        // 计算总油量和总消耗量
        for (int i = 0; i < n; i++) {
            sum_gas += gas[i]; // 累加油量
            sum_cost += cost[i]; // 累加消耗
        }

        // 如果总油量小于总消耗量，直接返回 -1
        if (sum_gas < sum_cost) return -1;

        // 遍历数组，选择起点
        for (int i = 0; i < n; i++) {
            // 累加当前加油站的油量和消耗量的差值
            sum += gas[i] - cost[i];

            // 如果当前油量小于 0，说明从当前起点无法绕完一圈
            if (sum < 0) {
                start = i + 1; // 更新起点为下一个加油站
                sum = 0; // 重置当前油量
            }
        }

        // 返回起点
        return start;
    }
};