贪心算法专题(八)：绝处逢生的起点—

哈喽各位，我是前端小L。

欢迎来到贪心算法专题第八篇！

题目描述很长，但核心很简单：

有一些加油站围成一个圈。

gas[i]：第i站有多少油。
cost[i]：从第i站开到第i+1站要耗多少油。
你有一辆油箱无限大的车。
目标：找一个起点，让你能绕圈跑完一周。如果找不到，返回 -1。

力扣 134. 加油站

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

题目分析：

输入：两个整数数组gas和cost。
输出：起始加油站的下标（唯一解）。

例子：

gas = [1, 2, 3, 4, 5]

cost = [3, 4, 5, 1, 2]

从下标 3（油4，耗1）出发：
- 到下标 4：剩 3，加 5，剩 8。耗 2。
- 到下标 0：剩 6，加 1，剩 7。耗 3。
- ... 一路顺风。返回 3。

核心思维：归零与跳跃

首先，有一个全局的硬性条件：

如果所有站点的总油量 sum(gas) 小于总消耗 sum(cost)，那神仙也跑不完一圈。直接返回 -1。

接下来是贪心的核心逻辑：局部最优推导。

我们维护一个 curSum（当前油箱余额）。

假设我们需要从 i 站出发。

我们计算gas[i] - cost[i]，这是这一站的净剩油量。
我们累加这个净剩量到curSum。
如果curSum < 0：
- 说明车在这一站（假设是j）抛锚了。
- 关键推断：从i到j之间的任何一个站点k，都不可能作为起点！
- 为什么？因为如果你从i出发，到达k时，你的油箱里一定有>= 0的油（否则你早在k之前就抛锚了）。带着这些“遗产”油你都在j站死掉了，如果你直接从k站白手起家（初始油量为0），你在j站只会死得更惨！
- 策略：既然i到j都不行，那我们就把起点设为j + 1，并把curSum归零，重新开始尝试。

[图解逻辑：A -> ... -> B (死) => 起点直接跳到 B+1]

算法流程

初始化：
- curSum = 0：当前连续路段的累积剩余油量。
- totalSum = 0：全局的总剩余油量（用于最后判断是否有解）。
- start = 0：我们假设的起点。
遍历所有加油站i：
- 计算当前站的净收益：rest = gas[i] - cost[i]。
- totalSum += rest。
- curSum += rest。
- 贪心判断：如果curSum < 0：
  - 说明从start到i这段路走不通。
  - 更换起点：start = i + 1。
  - 重置当前累积：curSum = 0。
最终判断：
- 循环结束后，如果totalSum < 0，说明总油不够，返回 -1。
- 否则，返回我们最后确定的start。（只要总油够，且我们找到了一段路能一直走到终点，那么数学上可以证明，从这个start绕回前面的路也是通的）。

代码实现 (C++)

C++

#include <vector> using namespace std; class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int curSum = 0; int totalSum = 0; int start = 0; for (int i = 0; i < gas.size(); i++) { // 计算当前站点的净剩油量 int rest = gas[i] - cost[i]; totalSum += rest; curSum += rest; // 贪心策略：如果累积油量小于0，说明从 start 到 i 的区间无法连通 if (curSum < 0) { // 之前的努力全部作废，起点重置为下一个点 i + 1 start = i + 1; // 油箱归零 curSum = 0; } } // 全局判断：如果总油量不够总消耗，肯定无解 if (totalSum < 0) { return -1; } // 否则，最后确定的 start 就是唯一解 return start; } };