0134. Gas Station ================= 题目信息 -------- :题号: 0134. 加油站 :难度: Medium :主题: 贪心、前缀和、环形数组、候选区间删除 :原题: `LeetCode 0134 `_ :重点: 将每站净油量分离出来,用总和判断全局可行性,并在一次失败时淘汰整段起点 题目重述 -------- 环形道路上有 ``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++ 实现 -------- .. code-block:: cpp #include class Solution { private: int simulateEveryStart( const std::vector& gas, const std::vector& cost ) { const int stationCount = static_cast(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(gas[station]) - cost[station]; if (tank < 0) { break; } ++traveled; } if (traveled == stationCount) { return start; } } return -1; } int eliminateFailedIntervals( const std::vector& gas, const std::vector& cost ) { long long totalBalance = 0; long long candidateBalance = 0; int candidateStart = 0; for (int station = 0; station < static_cast(gas.size()); ++station) { const long long balance = static_cast(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& gas, std::vector& 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`` 后的净量是: .. code-block:: text sum(k..i) = sum(start..i) - sum(start..k-1) 右侧第一项为负,第二项非负,所以结果一定为负。也就是说 ``start, start+1, ..., i`` 都无法越过站点 ``i``,无需逐个重试;下一个仍可能成功的候选只能从 ``i+1`` 开始。代码重置候选油量,因为新起点以空 油箱出发,不继承失败路线的负债。 具体走读区间删除 ~~~~~~~~~~~~~~~~ 对净变化 ``[-1, 2, -3, 4]``: .. list-table:: :header-rows: 1 * - 扫描站点 - 候选与累计油量 - 删除动作 * - ``0``,净量 ``-1`` - 从 ``0`` 得到 ``-1`` - 淘汰起点 ``0``,候选改为 ``1`` * - ``1``,净量 ``2`` - 从 ``1`` 得到 ``2`` - 保留候选 * - ``2``,净量 ``-3`` - 从 ``1`` 得到 ``-1`` - 同时淘汰 ``1``、``2``,候选改为 ``3`` * - ``3``,净量 ``4`` - 从 ``3`` 得到 ``4`` - 扫描结束 一次负前缀淘汰整段,正是线性算法删除逐起点重复模拟的来源。 为何最终候选能绕回数组开头 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 用全局前缀和 ``P`` 看,候选每次重置都发生在累计值创下新的严格低点之后,所以最终 ``candidateStart`` 位于全局最低前缀之后。从这个位置向数组末尾走,任意前缀相对最低点都非负。 绕回数组开头并走到位置 ``j`` 时,油量等于总净变化再加 ``P[j]`` 相对最低前缀的增量;前者由 ``totalBalance >= 0`` 保证非负,后者也非负。因此环形后半段的每个中间状态都不会欠油。区间淘汰得到的 候选配合总和条件,既是必要条件也是充分条件。 这里也解释了两个累加器的职责:``candidateBalance`` 只验证当前线性后缀,失败可清零;``totalBalance`` 必须保留所有站点的净量,最终负责判定环形拼接是否可能,绝不能随候选一起清零。 代码边界与主解选择 ~~~~~~~~~~~~~~~~~~ 若总和为负,扫描中留下的 ``candidateStart`` 只是一个局部后缀候选,公开函数必须返回 ``-1``。若总和 非负,最后一次失败不可能把候选留在数组外而没有后续补偿,否则所有已删除段之和为负、末尾又为空,总和 也会为负。单站且收支相等时累计值从不为负,候选保持 ``0``。 公开入口采用区间淘汰贪心:只扫描一次,时间 ``O(n)``、额外空间 ``O(1)``。逐起点模拟保留为正确性起点, 时间最坏 ``O(n^2)``。代码以 ``long long`` 累加净量,避免数组规模或单站数值扩大时总和溢出。