0134. Gas Station¶
题目信息¶
- 题号:
加油站
- 难度:
Medium
- 主题:
贪心、前缀和、环形数组、候选区间删除
- 原题:
- 重点:
将每站净油量分离出来,用总和判断全局可行性,并在一次失败时淘汰整段起点
题目重述¶
环形道路上有 n 个加油站。到达站点 i 可加入 gas[i] 单位汽油,从该站驶向下一站需要
cost[i] 单位。汽车从某个站以空油箱出发,在每站先加油再行驶;返回能顺时针完成一整圈的零基起点,
不存在则返回 -1。题目保证若解存在则唯一。
自建示例¶
gas = [2, 4, 1, 5]、cost = [3, 2, 4, 1]:每站净变化为[-1, 2, -3, 4], 从站点3出发时油量依次为4, 3, 5, 2,返回3;gas = [1, 2]、cost = [2, 3]:总汽油为3,总消耗为5,返回-1;gas = [3]、cost = [3]:从唯一站点出发恰好回到原处,返回0。
C++ 实现¶
#include <vector>
class Solution {
private:
int simulateEveryStart(
const std::vector<int>& gas,
const std::vector<int>& cost
) {
const int stationCount = static_cast<int>(gas.size());
for (int start = 0; start < stationCount; ++start) {
long long tank = 0;
int traveled = 0;
while (traveled < stationCount) {
const int station = (start + traveled) % stationCount;
tank += static_cast<long long>(gas[station]) - cost[station];
if (tank < 0) {
break;
}
++traveled;
}
if (traveled == stationCount) {
return start;
}
}
return -1;
}
int eliminateFailedIntervals(
const std::vector<int>& gas,
const std::vector<int>& cost
) {
long long totalBalance = 0;
long long candidateBalance = 0;
int candidateStart = 0;
for (int station = 0;
station < static_cast<int>(gas.size());
++station) {
const long long balance =
static_cast<long long>(gas[station]) - cost[station];
totalBalance += balance;
candidateBalance += balance;
if (candidateBalance < 0) {
candidateStart = station + 1;
candidateBalance = 0;
}
}
return totalBalance < 0 ? -1 : candidateStart;
}
public:
int canCompleteCircuit(
std::vector<int>& gas,
std::vector<int>& cost
) {
return eliminateFailedIntervals(gas, cost);
}
};
题解¶
先把加油与消耗合成一种状态变化¶
在站点 i 完成加油并驶向下一站后,油箱净变化固定为
balance[i] = gas[i] - cost[i]。从某个起点能否前进,只取决于沿途净变化的前缀和是否始终非负;绕一圈
后的最终变化则与起点无关,恒为 sum(balance)。
于是先得到一个必要条件:若总净变化为负,一圈消耗多于一圈补给,换任何起点都无法完成。总和非负还不能 直接告诉我们从哪里出发,但它把“是否可能”与“候选位置”分成了两个可独立维护的量。
原始方案:逐个起点完整模拟¶
simulateEveryStart 对每个站点把油箱清零,按环形下标继续,首次负油时停止。它直接验证了题意,也能找到
答案;问题是相邻起点会重复走相同区间。若许多起点都在接近一圈时才失败,最坏要检查 O(n^2) 个站点。
失败不只淘汰当前起点¶
假设当前候选为 start,从它出发到站点 i 后,candidateBalance 第一次变为负。在此之前,从
start 到任意 k-1 的累计值都非负。对区间内另一个起点 k,走到 i 后的净量是:
sum(k..i) = sum(start..i) - sum(start..k-1)
右侧第一项为负,第二项非负,所以结果一定为负。也就是说 start, start+1, ..., i 都无法越过站点
i,无需逐个重试;下一个仍可能成功的候选只能从 i+1 开始。代码重置候选油量,因为新起点以空
油箱出发,不继承失败路线的负债。
具体走读区间删除¶
对净变化 [-1, 2, -3, 4]:
扫描站点 |
候选与累计油量 |
删除动作 |
|---|---|---|
|
从 |
淘汰起点 |
|
从 |
保留候选 |
|
从 |
同时淘汰 |
|
从 |
扫描结束 |
一次负前缀淘汰整段,正是线性算法删除逐起点重复模拟的来源。
为何最终候选能绕回数组开头¶
用全局前缀和 P 看,候选每次重置都发生在累计值创下新的严格低点之后,所以最终
candidateStart 位于全局最低前缀之后。从这个位置向数组末尾走,任意前缀相对最低点都非负。
绕回数组开头并走到位置 j 时,油量等于总净变化再加 P[j] 相对最低前缀的增量;前者由
totalBalance >= 0 保证非负,后者也非负。因此环形后半段的每个中间状态都不会欠油。区间淘汰得到的
候选配合总和条件,既是必要条件也是充分条件。
这里也解释了两个累加器的职责:candidateBalance 只验证当前线性后缀,失败可清零;totalBalance
必须保留所有站点的净量,最终负责判定环形拼接是否可能,绝不能随候选一起清零。
代码边界与主解选择¶
若总和为负,扫描中留下的 candidateStart 只是一个局部后缀候选,公开函数必须返回 -1。若总和
非负,最后一次失败不可能把候选留在数组外而没有后续补偿,否则所有已删除段之和为负、末尾又为空,总和
也会为负。单站且收支相等时累计值从不为负,候选保持 0。
公开入口采用区间淘汰贪心:只扫描一次,时间 O(n)、额外空间 O(1)。逐起点模拟保留为正确性起点,
时间最坏 O(n^2)。代码以 long long 累加净量,避免数组规模或单站数值扩大时总和溢出。