抚州市网站建设_网站建设公司_UI设计师_seo优化

哈喽各位，我是前端小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 站出发。

1. 我们计算gas[i] - cost[i]，这是这一站的净剩油量。

2. 我们累加这个净剩量到curSum。

3. 如果curSum < 0：

   • 说明车在这一站（假设是j）抛锚了。

   • 关键推断：从i到j之间的任何一个站点k，都不可能作为起点！

   • 为什么？因为如果你从i出发，到达k时，你的油箱里一定有>= 0的油（否则你早在k之前就抛锚了）。带着这些“遗产”油你都在j站死掉了，如果你直接从k站白手起家（初始油量为0），你在j站只会死得更惨！

   • 策略：既然i到j都不行，那我们就把起点设为j + 1，并把curSum归零，重新开始尝试。

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

算法流程

1. 初始化：

   • curSum = 0：当前连续路段的累积剩余油量。

   • totalSum = 0：全局的总剩余油量（用于最后判断是否有解）。

   • start = 0：我们假设的起点。

2. 遍历所有加油站i：

   • 计算当前站的净收益：rest = gas[i] - cost[i]。

   • totalSum += rest。

   • curSum += rest。

   • 贪心判断：如果curSum < 0：

     • 说明从start到i这段路走不通。

     • 更换起点：start = i + 1。

     • 重置当前累积：curSum = 0。

3. 最终判断：

   • 循环结束后，如果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级别题目，也是面试中的“终极杀手”。

• 一群孩子排排坐，每个孩子有评分。

• 每个孩子至少一颗糖。

• 相邻的孩子，评分高的必须获得更多的糖果。

• 问最少需要多少糖？

这道题难就难在“相邻”是双向的（既要比左边多，又要比右边多）。

贪心策略教我们：不要试图同时顾及两边！ 我们可以先从左往右遍历一次（只顾左边），再从右往左遍历一次（只顾右边），最后取最大值。

准备好分糖果了吗？下期见！