：绝处逢生的起点——「加油站」)
哈喽各位，我是前端小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; } };深度复杂度分析
时间复杂度：O(N)
我们只需要遍历一次数组。
这比暴力法的 $O(N^2)$ 简直是质的飞跃。
空间复杂度：O(1)
只需要几个变量。
总结：相信数学，相信贪心
这道题最难理解的地方在于：为什么 totalSum >= 0 且 curSum 在最后一段非负，就一定能保证绕圈成功？
这涉及到一个数学证明：如果总和非负，那么一定存在一个起点，使得所有前缀和非负。我们通过贪心策略抛弃了所有“前缀和为负”的区间，剩下的那个起点，就是那个“天选之子”。
贪心算法在这里表现为：遇到困难（负数），立刻止损，跳过整段困难区间，寻找新的希望。
下一题预告：分发糖果
接下来这道题是贪心算法的Hard级别题目，也是面试中的“终极杀手”。
一群孩子排排坐，每个孩子有评分。
每个孩子至少一颗糖。
相邻的孩子，评分高的必须获得更多的糖果。
问最少需要多少糖？
这道题难就难在“相邻”是双向的（既要比左边多，又要比右边多）。
贪心策略教我们：不要试图同时顾及两边！ 我们可以先从左往右遍历一次（只顾左边），再从右往左遍历一次（只顾右边），最后取最大值。
准备好分糖果了吗？下期见！
