企业官网建设流程全解析

前阵子一个准备算法面试的朋友跟我抱怨：“贪心算法刷了二十道题，还是觉得玄学。对着题解看，每个局部最优的选择都很有道理；自己上手写，样例一多就翻车。”这个感受我太熟悉了。力扣hot100里贪心相关的题其实不多，撑死了六七道，但每道都极其典型，覆盖了面试里最高频的几个模型：股票买卖、跳跃游戏、区间贪婪、环形数组判定。把这些题吃透，比无脑刷五十道零散的贪心题有用得多。

这篇博客我打算把hot100里贪心相关的题目全部过一遍，按模型分类拆解，每个模型讲清楚三件事：贪心策略是什么、为什么是对的、边界条件容易错在哪。适合两类人看：一类是准备大厂算法面试、时间紧任务重的同学；另一类是刚开始刷力扣、对贪心只有一个模糊概念的新手。

1. 先看全局：贪心在hot100里到底占多少、考什么

1.1 hot100里的贪心题，数量不多但模型非常集中

以目前常见版本的力扣Hot 100题目清单来看，能被明确归入“贪心算法”标签的题大致是这几道：

另外像“根据身高重建队列（406）”这类题，虽然很多题单把它归进贪心标签，但它本质上考的是“排序后按规则插入”，贪心成分很弱，更像是自定义排序+插队的综合题。我在刷题时更倾向于把它归为排序专题，这里也就不展开说了。

还有一个特殊的坑：有人会在讨论区问“腐烂的橘子是什么题型”。这题用的是多源BFS（广度优先搜索），不是贪心。它虽然问的是“最少分钟数”，但扩散过程天然适合按层模拟，按贪心去解反而容易漏掉多源同时扩散的情况。这部分我在第4章详细讲，先把结论放在这里——贪心在hot100里的出题范围非常窄，窄到完全可以集中突破。

1.2 贪心的底层逻辑：什么时候局部最优能推出全局最优

很多人对贪心恐惧，是因为它不像动态规划那样有固定的状态转移方程。动态规划是把所有可能的状态都算一遍，贪心则是每步只做一个选择，不做回头路。要想用贪心，题目必须满足一个隐藏前提：每一步的局部最优选择，恰好也是全局最优解的一部分。这个前提在数学上叫“最优子结构”和“贪心选择性质”。

举个生活中的例子你就明白了。假设你下午要开会，会议室里有若干个时间段可预订，每个时间段都有开始时间和结束时间，你想安排尽可能多的会议。最直观的策略是什么？每次选“结束时间最早”的那个会议。为什么？因为结束得越早，给后面留下的可用时间就越长，这个选择不会让整体安排变差。这就是一个教科书级的贪心模型，local choice决定了全局结果。

反例也很容易举：自助餐拿菜。如果每次都选当前看起来最好吃的那一口，最后可能吃撑了还没吃到真正想吃的，因为胃容量有限。这说明“当前最优”并不总是能推出“全局最优”。刷贪心题的过程，说白了就是在训练你识别“哪些问题满足那个前提，哪些不满足”。hot100里的这几道题，全都是满足前提的经典模型，所以非常适合用来建立直觉。

2. 六道经典题拆解：每一道都代表一类模型

2.1 股票买卖系列：121和122的差别就是“一次”和“无数次”

这两个题放一起对比刷，效果最好。121题只允许一次交易，也就是你只能挑一天买入、之后挑一天卖出，求最大利润。最经典的贪心解法是一遍遍历：记录遍历到今天为止出现过的最低价格，然后计算“如果今天卖出能赚多少”，不断更新最大值。

class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 min_price = prices[0] max_profit = 0 for price in prices[1:]: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit

为什么这个局部记录是有效的？因为对于任意一天的卖出动作，想获得最大利润，买入日一定是之前价格最低的那一天，这是无可争议的最优前置条件。我们不需要知道具体哪一天买入，只需要维护“截至目前的最低价”这个状态就够了。复杂度O(n)时间、O(1)空间，是这个题最优解。

122题则是无限次交易，你可以今天买明天卖，也可以持有多天再卖，唯一限制是手里同时只能有一支股票。这个题的贪心策略一句话就能说清：只要今天的价格比昨天高，就认为这一段差价可以赚到。

class Solution: def maxProfit(self, prices: List[int]) -> int: profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i - 1]: profit += prices[i] - prices[i - 1] return profit

这里有个很多人想不通的点：股票交易不是应该“低买高卖”吗？为什么每天比较相邻差价也算？你拿个三段价格 [1, 3, 5] 试一下就明白了。一次交易买1卖5赚4；分两次交易买1卖3、买3卖5，总共赚(3-1)+(5-3)=4。结果一样。也就是说，任意一段单次交易的大利润，可以被拆成一串相邻差价的和。既然题目允许无限次交易，把所有正差分累加就是上界，而累加所有正差分显然可达，所以这就是最优解。

注意：121题的解法本质上也可以理解为“DP的滚动优化”，但大部分人接受它作为贪心入门题更自然。后面会细说贪心和DP的边界问题。

2.2 跳跃游戏系列：维护“最远可达边界”就够了

55题（跳跃游戏）问的是：从下标0出发，每个位置上的数字代表你最多能往后跳多少步，能不能跳到最后一个位置。这个题的贪心策略叫“维护可达最远距离”。

class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) farthest = 0 for i in range(n): if i > farthest: return False farthest = max(farthest, i + nums[i]) if farthest >= n - 1: return True return True

核心思路极简单：遍历每个位置，如果当前位置已经在可达范围内（i <= farthest），就尝试更新最远可达边界；一旦发现某个位置根本够不到（i > farthest），说明中间出现了断点，直接返回False。为什么贪心成立？因为“能到达的最远位置”是一个单调不减的上界，我们不需要具体走哪条路径，只要这个上界能覆盖终点，就必然存在一条合法路径。这题不做路径规划，只做可行性判定，所以贪心是自然的。

45题（跳跃游戏 II）升级了，要求返回到达终点的最小跳跃次数。这题贪心解法有点像“按层推进”的BFS：把当前位置能跳到的最远位置看成一层的右边界，走到边界时计一次跳跃，然后更新边界为下一层能到达的最远位置。

class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) if n == 1: return 0 steps = 0 cur_end = 0 # 当前这一跳能到达的右边界 farthest = 0 # 下一跳能达到的最远位置 for i in range(n - 1): farthest = max(farthest, i + nums[i]) if i == cur_end: steps += 1 cur_end = farthest if cur_end >= n - 1: break return steps

这里最容易翻车的是循环边界。我在写第一版时习惯遍历整个数组，结果在最后一个位置时又触发了一次跳跃计数，多算一步。后来发现循环只需要走到 n - 2 就可以，或者像上面代码里一样遍历到 n - 1 但通过 break 退出。只要记住：到达最后一个位置后就不需要再跳了，这类边界问题就能避免。

45题为什么能贪心而不是必须DP？因为每一步选择“能跳得最远”的那些位置集合，不会因为之前的跳跃方式而变小；跳到最远意味着给后续留下的选择空间最大，所以跳数一定不会比保守策略多。

2.3 划分字母区间：先记录每个字符的最后出现位置

763题“划分字母区间”是hot100里比较有意思的一道题：给你一个字符串，要把字符串划分成尽可能多的片段，要求同一字母最多只出现在一个片段中，返回每个片段的长度。

我第一次见这道题时完全没思路，后来理解了核心思想就发现它特别简单：先扫一遍字符串，记录每个字符最后一次出现的下标。然后再扫一遍，维护当前片段的一个右边界end，每遇到一个字符，就把end更新为max(end, 该字符最后一次出现的下标)。当遍历的位置i等于end时，当前位置就是片段边界，切一刀。

class Solution: def partitionLabels(self, s: str) -> List[int]: last = {} for i, ch in enumerate(s): last[ch] = i res = [] start = end = 0 for i, ch in enumerate(s): end = max(end, last[ch]) if i == end: res.append(end - start + 1) start = end + 1 return res

这个策略为什么是贪心？因为每个字符的最后一次出现位置，是一个不能突破的硬约束。当前片段里只要包含某个字符，片段的右边界就必须至少延伸到该字符的最后出现位置。在每步中，我们都把右边界推到这个约束的最大值，因此不会漏掉任何必须包含的字符，也不会产生不必要的更长片段。当i走到end时，说明当前片段已经“被迫完整”了，此时切割就是题目允许的最早切割点，能保证片段数量最多。

这个模型和45题的farthest变量本质上是一回事：维护一个不断向右推进的目标边界，等到遍历指针撞上边界时做一次操作。模型识别出来之后，两道题就是同一套思路。

2.4 加油站：环形数组上的贪心结论

134题“加油站”长这样：在一个环形路线上有若干加油站，第i个加油站有gas[i]升油，从第i站开到第i+1站需要消耗cost[i]升油。你的车一开始油箱是空的，问从哪个站出发能走完全程，如果不存在则返回-1。

这题贪心解法的代码非常短，但背后的推理值得好好讲一遍。

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: total = 0 cur = 0 start = 0 for i in range(len(gas)): diff = gas[i] - cost[i] total += diff cur += diff if cur < 0: start = i + 1 cur = 0 return start if total >= 0 else -1

第一部分：算总账。把所有站的gas减cost加起来，如果总和小于0，说明整条路的油量供应不足，直接返回-1。这个判定是全局性的，也是必要条件。

第二部分：确定起点。从0开始模拟，维护一个cur变量表示当前累计的剩余油量。当cur小于0时，说明从当前start到i之间的任何站点都不能作为起点，因为从任何一个站点出发，走到i这里油都会耗尽。因此直接把起点重置为i+1，cur归零重新累计。

为什么“从start到i之间任何站点都不能作为起点”？这一点是很多人卡住的点。假设起点是j（start <= j <= i），从j出发的剩余油量可以看作从start出发到j时已有的油量，再加上j到i这段的增量。既然从start出发到i时总量为负，那么任意j到i的子段也至少有一个点是负的，也就是说会在i或i之前断油。所以直接跳过整个区间，从i+1重新尝试是安全的。

这个结论很反直觉，但配合一个例子就清楚了。用gas = [1,2,3,4,5], cost = [3,4,5,1,2]手动推一遍：从0开始，diff数组是[-2, -2, -2, 3, 3]，cur在前三站就变成-6，start跳到3，cur重置，3+4+5=3, 3+3-1-2=3，走完整圈。结果返回3，正确答案。

3. 实操心法：怎么判断一道题能不能贪心，以及怎么证明

3.1 三个信号帮你快速锁定贪心

刷题量上来以后，我判断一道题能不能用贪心，基本看三个信号。

第一，题目问的是“最大值”“最小值”“是否可行”“最少次数”这类极值或判定问题。这是贪心的常见出题面。如果是“求所有方案中满足条件的那一个”或者“求具体方案数量”，那大概率是回溯/DP，而不是贪心。

第二，决策的每一步不会改变后续可选集合的结构，只改变一个单调推进的量。比如55题和763题，核心都是维护一个不断向右推进的边界，前面的决策不会“绕回去”影响边界上限。一旦你发现前面的选择会改变后面状态的计算方式，比如背包问题里选不选当前物品会影响剩余容量，那贪心就危险了，应该考虑DP。

第三，题目存在一个明显的“排序/取最值”先手动作。比如活动选择按结束时间排序，122题按相邻差价取正，134题找第一个油量为负的断点。这类题十有八九是贪心。

满足这三个信号，先按贪心写；写出来样例过不了，再换DP或者回溯。这个流程在面试时非常高效，因为大多数面试官期待的就是你先判断题型再动手，而不是上来就写状态转移。

3.2 交换论证：面试现场证明贪心正确性的实用方法

很多人面试时能写出贪心解法，但被问“为什么这样是对的”就卡壳。这里分享一个最实用的证明工具：交换论证法。核心思想是：假设存在一个最优解，如果这个最优解的第一步或某个位置和我们贪心选择的方案不一样，通过交换它们，最优解不会变差。反复交换后，最优解就变成了贪心解。

拿活动选择举例。假设存在一个最优解，第一个选择的活动不是结束时间最早的A，而是另一个活动B。由于A结束时间不晚于B，把B换成A后，A占用的时间区间不会超过B，因此后续所有活动依然可以和A搭配。这样得到的解仍然是一个合法解，活动数量没有减少。既然如此，最优解完全可以被改造成一个“第一步就是贪心选择”的解。接着对后续步骤做同样的交换，最后就得到贪心解。所以贪心解就是最优解。

面试时不要求你写出严格的数学证明，能把交换论证的逻辑说清楚就够用了。这比背一堆结论强得多——因为题目一变，结论就失效，但证明逻辑能复用。

3.3 推荐刷题顺序：从易到难的梯度安排

如果时间有限，我的建议是严格按照这个顺序刷：

1. 先做121，再做122。感受“一次交易拆成无限次交易”的思维跳跃；
2. 再做55，再做45。感受“可不可达”和“最少步数”的差异；
3. 然后做763，训练“区间边界维护”的模型；
4. 最后做134，因为它带有环形数组和数学结论，是这几道里最需要推理的一题。

整体节奏上，这些题如果每天投入两小时，三天内可以全部吃透。但“吃透”的定义不只是AC，而是每道题都能不看题解重新推一遍，并且能用自己的话讲清楚贪心策略为什么正确。做完这一步，你面对面试里绝大多数贪心题，至少能快速判断出“这题能不能贪”了。

4. 高频问题与翻车现场：这些坑我替你踩过了

4.1 贪心和动态规划怎么区分？很多题其实两解

我见过最多的疑问就是“这题我用了DP，怎么题解里说是贪心”。这两者的关系不是互斥的。贪心是DP在满足“贪心选择性质”时的一种特例，剪掉了大量状态只用最优状态推进。DP则是把可能的状态全部保留下来，用状态转移保证最优。

区分它们有个简单套路：决策时，如果我只需要知道“当前最优的一个值”，不需要知道“所有可能的值”，那就是贪心；如果每一步都需要保留多种状态，比如背包问题里容量不同导致结果不同，那就是DP。121题两种方法都能解，用“记录历史最低价+当前利润”就是贪心视角，定义dp[i]为第i天卖出的最大利润再做转移就是DP视角。两种解法的复杂度一样，但思维方式不同，面试时你能说清任意一种都行。

4.2 腐烂的橘子为什么不算贪心？先把题型标签认清楚

“力扣腐烂的橘子是什么题型”这个问题经常出现在力扣相关搜索热词里。说清楚：994题腐烂的橘子属于多源BFS，不是贪心。原因在于它求的是“所有橘子腐烂需要的最少分钟数”，这个分钟数由扩散层数决定。BFS天然逐层扩散，每扩散一层就是一分钟，所以BFS就是最契合的解法。贪心在这里没有用武之地——因为每一分钟扩散的源头是多个，选择哪个橘子先腐烂并不会改变扩散速度，不存在“局部最优决策点”。这个题也提醒我们：刷题时别只看题目问“最少/最长”就默认是贪心，先想想问题的结构适不适合逐层模拟或者图论遍历。

4.3 边界条件与细节坑：三道题里的典型错误

以下几个坑是我（以及身边很多人）在刷这几道题时真实踩过的，整理出来方便自查：

• 55题和45题在nums长度为1时，前者直接返回True，后者直接返回0。很多思路版本没做这个特判，会导致循环逻辑额外跳一次。
• 45题里的cur_end和farthest更新顺序很容易写反。正确顺序是：先不断更新farthest，等到i撞到cur_end时再步数+1并把cur_end设为farthest。如果一开始就把cur_end更新了，后面i就永远撞不到边界了。
• 134题容易忘记total的全局判断。有些人只做了局部模拟，当某个局部cur小于0时重置start，最后直接返回start，其实如果total < 0，这个start是走不完一圈的。所以必须先有total >= 0这个前提，或者最后返回前再判断一次。
• 763题要注意start重置的位置。切完一个片段后，start应该设为end + 1，而不是end。这个错误我在白板面试时犯过一次，非常尴尬。

这些小细节单独看都不难，但组合起来就是“样例过、提交挂”的重灾区。所以刷这些题时，我建议刻意多准备几组边界用例来验证：空数组、单元素数组、全相同字符、全零数组等。

我个人刷完这组题之后的体会是：贪心很少考智商，更多是考模型积累。你见过“维护最远边界”这个模型，45题就是送分题；没见过，可能想半小时都对着样例发懵。所以建议把这六道题当成模板题来背，但背的不是代码，而是“为什么这个局部选择是安全的”那段论证逻辑。等你把这个问题想明白了，hot100里的贪心部分就算真正过关了。