企业官网建设流程全解析

LeetCode Hot 100里的贪心算法题，数量不多，加起来也就十几道，但每一道都是面试高频。我刷到贪心这一块的时候有个很直观的感受：代码往往不超过十五行，可一旦想不明白为什么这么做是对的，就会陷入“这个贪心我见过、但下次换个包装我又不认识了”的恶性循环。所以这篇文章我不打算只贴题解，而是把Hot 100里的贪心题按题型拆开，从算法导论的两个核心性质讲起，逐题给思路、代码和证明思路，再聊一聊周赛和真实面试里怎么识别贪心、怎么避免踩坑。如果你正在准备算法面试，或者已经刷完链表、二叉树想集中突破贪心，这篇文章应该能帮你把“会做某道题”升级成“会判断一类题”。

1. 贪心算法到底是什么：从“短期最优”到“全局最优”

1.1 算法导论的两个核心性质：贪心选择与最优子结构

很多人对贪心的理解停留在“每一步选当前最优”，这个说法没错，但容易让人误以为贪心靠的是直觉和运气。算法导论第16章用了整整一章讲贪心算法，核心就落在两个性质上：贪心选择性质和最优子结构。贪心选择性质说的是，你可以通过一系列互不后悔的局部最优选择，最终得到全局最优解；最优子结构说的是，一个问题的最优解里包含了子问题的最优解，换句话说，你不需要回头调整之前做过的选择，后面每一步只需要在当前剩余问题上继续做局部最优。

我用吃自助餐来类比：每次只取当下最想吃的一盘，取完之后不换回去，最终得到的就是“对这次取餐顺序来说最满意的一套”。但这套逻辑能成立，前提是“当前最想吃的”永远包含在某个全局最优方案里。贪心算法真正的难点就在这里——你必须验证这个前提，验证不了，局部最优就会把全局最优带偏。

这两条性质不是孤立存在的。最优子结构是动态规划也需要的，贪心比动态规划更苛刻的地方在于：动态规划会枚举所有可能的子问题，贪心却要求每一步都能确定性地减少问题规模，而且这个减少方式恰好是全局最优的。所以贪心可以理解为动态规划的一种特化，只不过这种特化一旦成立，复杂度往往就能从多项式级别降到一个排序或者一趟扫描的级别。

1.2 贪心 vs 动态规划：什么时候能“偷懒”

算法导论里有个经典例子非常能说明问题：活动选择问题。给你一组活动，每个有开始时间和结束时间，活动之间不能重叠，目标是选出尽可能多的活动。按结束时间从小到大排序，每次选结束最早且与已选活动不冲突的那个，这就是贪心。但如果给每个活动加一个权重，目标改成“选出总权重最大的相容集合”，贪心就立刻失效了，必须用加权区间调度的动态规划。两个问题只差一个权重，解法就从贪心跳到了动态规划。

这个例子对我来说是理解贪心边界最好的入口。它说明贪心并不是“动态规划的弱化版”，而是“满足特定结构时的最优解法”。当你看到一道最优化题，先别急着上动态规划，要问自己：这个问题在每一步做完选择之后，剩下的子问题是不是完全独立？如果独立，再想一想“当前最优是否一定不劣于其他选择”，如果能证明，贪心就比DP省太多代码和复杂度。

判断一个题能不能贪心，我常用一个土办法：把候选策略写在纸上，然后强行构造反例。如果怎么构造都构造不出来，再想想能不能用交换论证法证明；如果反例很容易构造出来，那就老老实实回去写动态规划。这个土办法虽然朴素，但它逼着你去理解问题的结构，而不是背模板。

2. LeetCode Hot 100里贪心考点分布：三种典型题型

2.1 高频题清单：一眼看出考察方向

我粗略数过Hot 100官方题单里的贪心题，主要集中在三个方向上：序列最优类、区间调度类、排序构造类。序列最优类里最典型的是55跳跃游戏、45跳跃游戏II、122买卖股票的最佳时机II、134加油站；区间调度类有763划分字母区间、435无重叠区间、452用最少数量的箭引爆气球；排序构造类则是406根据身高重建队列、455分发饼干、860柠檬水找零。这些题表面千差万别，但底子都是同一个东西——每次做一个确定性的局部选择，这个选择直接决定后续的剩余问题。

这张表自己会说话：凡是能用贪心解决的Hot 100题，要么依赖一个排序，要么依赖一趟线性扫描，几乎不会出现两层循环嵌套的暴力优化。原因是贪心的本质决定了你不需要回头比较，所以复杂度天然就低。如果你看到一个题，你的解法需要反复回退或者重新尝试，那大概率不是贪心的用武之地。

2.2 三步判断法：如何快速决定“能不能贪心”

我在面试和刷题时总结了一个三步判断法，虽然不保证百分之百准确，但帮我避掉了很多假贪心。第一步，把候选的局部策略写出来，找一个小例子手动走一遍，看结果是否合理；第二步，认真尝试构造反例，想想是否存在“局部最优导致全局更差”的情况，如果能构造出来，直接放弃贪心；第三步，如果构造不出反例，尝试用交换论证法或者数学归纳法把正确性补齐，补不上就继续存疑。

贪心还有个常见判断依据叫无后效性：做过的选择不会影响后面选择的可行性，或者说影响是可控的、确定的。一旦发现后续选择需要根据前面的选择结果动态调整，就要立刻警惕。比如跳跃游戏里，你维护的“最远可达位置”是单调递增的，前面的选择不会让后面的可达范围变小，这就是典型的无后效性；而零钱兑换里，你前面用掉多少枚硬币会直接影响后面还能用多少，这时候就要考虑动态规划了。

这三个步骤加起来最多花五分钟。五分钟换来的是不踩坑，我认为非常值。尤其是面试时，你说“这道题我想用贪心，原因是我构造不出反例，而且局部选择不会影响后续”，这一句话就能让面试官知道你不是在背题，而是真的理解贪心的边界。

3. 高频题逐题拆解：思路、代码与边界

3.1 股票类：122买卖股票的最佳时机II

122题的场景是：给你一个价格数组，可以多次买卖，但任何时候最多持有一股，求最大利润。很多人第一次看会觉得这是动态规划，实际上它是最典型的贪心变体。核心思路极其简单：只要今天的价格比昨天高，就把这个价差计入利润，把数组中所有正向相邻差值加起来就是答案。

为什么敢这么算？因为允许“今天卖、明天买”这种切分操作，持有一股的限制并不会阻断你把一段连续上涨拆成若干段正差价。比如价格从1涨到4，整体利润是3，拆成每天的正差价1+1+1还是3；如果中间有一天下跌，差价是负数，直接跳过它就行，因为跳过下跌等于没有交易，不会产生额外成本。这个转化不是模拟真实交易，而是数学上的等价变换，代码自然短。

def maxProfit(prices): total = 0 for i in range(1, len(prices)): if prices[i] > prices[i - 1]: total += prices[i] - prices[i - 1] return total

要注意一个细节：有些题解把判断条件写成max(0, prices[i] - prices[i-1])，效果一样，但我个人更喜欢显式判断，因为面试时更好讲清楚“正向差价累加”的逻辑。另外这道题在Hot 100里通常被归到“数组/动态规划”分类下，但它真正的思维核心是贪心的区间切分思想，和121题只能买卖一次不一样。121需要维护历史最低点，属于扫描维护最值，不是纯贪心，别把两题混着背。

3.2 跳跃类：55和45从“能不能到”到“最少几步”

55跳跃游戏问的是：从数组第一个位置出发，每个位置记录你能往后跳的最大长度，能不能跳到最后一个下标。贪心做法只维护一个变量reach，表示当前能到达的最远下标，遍历数组时，如果当前位置i已经大于reach，说明中间断了，直接返回False；否则不停更新reach = max(reach, i + nums[i])。遍历结束reach如果覆盖了最后一个下标，就返回True。

这个解法看起来简单到不像话，但关键在于理解“可达范围是单调的”：只要reach更新过，前面的所有位置都已经被覆盖检查过，不需要回头。所以一个变量就够，连DP数组都不需要。

def canJump(nums): reach = 0 for i, jump_len in enumerate(nums): if i > reach: return False reach = max(reach, i + jump_len) return True

45跳跃游戏II把题目改成“最少跳几次能到最后一个下标”，难度立刻上一个台阶。我一开始想用DP，后来发现有个非常巧妙的贪心视角：把每一次跳跃当成一层BFS，当前层是你现在能到达的所有下标，你在这一层里找出能抵达的最远下标作为下一层的边界，当遍历指针i走到当前层边界时，跳跃次数加1，边界更新成下一层最远。这样每一步都“挑能跳最远的”，次数自然最少。

def jump(nums): 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

代码里有两个边界细节要特别小心。一是循环范围是range(n - 1)而不是range(n)，因为一旦到达最后一个下标就不需要再跳了；二是cur_end的更新时机，必须在i == cur_end时才加步数，否则会把同一层内的跳跃重复计数。我见过不少人在这个边界上翻车，导致结果多出一跳。

3.3 区间类：763划分字母区间与435无重叠区间

763划分字母区间是我非常喜欢的一道题，因为它把贪心藏在了字符串里。题目要求把字符串划分成尽可能多的片段，每个字母只能出现在一个片段里。解法分两步：第一次遍历记录每个字符最后一次出现的下标；第二次遍历维护当前片段的右边界，每次取当前字符的最后位置来扩展边界，当遍历指针i正好等于边界时，说明这个片段可以闭合，记录长度后重置起点。

为什么“能闭合就闭合”是最优的？因为闭合得越早，片段就越短，在满足“每个字母只出现在一个片段”的约束下，片段数量就越多。这是一个非常直观的贪心选择：局部上你让每个片段尽可能短，全局上就得到最多片段数。交换论证法也可以证明，把任意一个片段向后延长都不会让总数量变多。

def partitionLabels(s): last = {c: i for i, c in enumerate(s)} res = [] start = 0 end = 0 for i, c in enumerate(s): end = max(end, last[c]) if i == end: res.append(end - start + 1) start = end + 1 return res

435无重叠区间则是区间排序贪心的代表。给定一组区间，要求移除最少的区间使剩余区间不重叠。贪心策略是按右端点升序排序，然后保留结束最早的区间，跳过所有与它重叠的区间。这个策略的直觉很简单：右端点越早结束，留给后面区间的空间就越大。代码里用last_end记录当前保留区间的右端点，一旦发现当前区间左端点小于last_end，说明重叠，计数加1；否则更新last_end为当前区间的右端点。

def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(key=lambda x: x[1]) last_end = intervals[0][1] count = 0 for i in range(1, len(intervals)): if intervals[i][0] < last_end: count += 1 else: last_end = intervals[i][1] return count

这里有个很容易被忽略的坑：排序键选右端点而不是左端点。如果按左端点排序，你保留的区间可能是“开始很早但结束很晚”的，它会压掉一大片后续区间；按右端点排序才能保证每次保留的都是“最容易不占空间”的。这一点在452用最少数量的箭引爆气球里也一样，箭的题本质上就是统计不重叠区间的数量，策略完全相同。

3.4 入门构造类：455分发饼干与860柠檬水找零

455分发饼干是贪心里最友好的入门题。孩子的胃口数组g，饼干尺寸数组s，每个孩子最多给一块饼干，饼干尺寸大于等于胃口就能满足，问最多能满足几个孩子。贪心策略是把两个数组都排序，然后从小到大匹配：用尽可能小的饼干去满足胃口最小的孩子。这个策略好就好在“不浪费大饼干”，因为大饼干留给后面的孩子机会更多。

def findContentChildren(g, s): g.sort() s.sort() i = 0 for cookie in s: if i < len(g) and cookie >= g[i]: i += 1 return i

860柠檬水找零稍微有点脑筋急转弯的味道。顾客付5、10、20三种面额买5美元柠檬水，你一开始没有零钱，判断能否给每个顾客正确找零。贪心点在于：找15美元时，优先用10美元加5美元的组合，而不是三张5美元，因为5美元是最稀缺的通货，要省着用。

def lemonadeChange(bills): five = ten = 0 for bill in bills: if bill == 5: five += 1 elif bill == 10: if five == 0: return False five -= 1 ten += 1 else: if ten > 0 and five > 0: ten -= 1 five -= 1 elif five >= 3: five -= 3 else: return False return True

这类“模拟+贪心”题，代码都不难，难的是你要想清楚为什么“优先用大面额”是安全的。它本质上是在保护稀缺资源，和区间调度里“保留早结束的区间”是同一个思想——优先消耗那些“对后续限制更小”的选项。把这些题串起来就会发现，贪心题并不是一堆孤立的脑筋急转弯，而是几个核心思想的排列组合。

4. 正确性证明、周赛变形与面试讲解技巧

4.1 交换论证法：给贪心证明打底

很多刷题的人看到贪心题就直接写代码，写完一提交发现过了，就认为自己懂了。但面试时面试官大概率会追问一句“你为什么觉得这是对的”，这时候如果你答不上来，前面的代码再漂亮也会打折扣。我给自己的要求是：Hot 100里的每道贪心题，都要能说出一句证明思路，最常用的就是交换论证法。

交换论证法的步骤很固定：假设贪心解G不是最优解，取一个最优解O；找到G和O第一个不同的决策点；把O里这个位置的选择“交换”成G的选择；证明交换之后O不会变差；反复交换，最后O就变成了G，得出G也是最优解，与假设矛盾。活动选择问题就是教科书级的例子：贪心选了最早结束的活动a，如果最优解第一个活动是b，那么b的结束时间一定不晚于a（因为你按结束时间排序后a是最早的），把b换成a，后面的活动依然都能安排下，数量不变，所以贪心选择不劣于任何最优解的第一选择。

这个方法最优雅的地方在于，它让你把“证明”变成一种机械化操作，而不是靠灵感。你可以先用交换论证法在草稿纸上验证任何贪心策略，验证通过再动手写代码。Hot 100里的股票差分、跳跃边界、区间右端点排序，全部都能用交换论证法打通，建议你至少把763和435两道的证明过程自己写一遍，写完再遇到同类题会很踏实。

4.2 周赛430式的包装题：怎么把贪心从壳里剥出来

很多人刷完Hot 100去做周赛，会发现一个扎心的事实：题面包装越花，你越难认出它到底考什么。拿周赛430这一档的场次来说，第三题第四题经常是“选择若干物品使某指标最大”“把数组分成若干段满足某限制”这类看起来像是贪心的题，实际上确实有很多就是Hot 100经典题的变体，只是穿了一层“必须成对”“必须连续”“必须满足高度差”的外壳。

我的处理流程是先把题目的壳剥掉，抽象成三个问题：决策变量是什么？选择之间是否互相影响？是否存在一个自然的排序规则？如果决策变量是一个个元素，元素之间没有强耦合，而且能找到一个排序规则让局部最优不劣于其他选择，那大概率是贪心。最典型的变形方式有两种：一种是把区间调度变成“你需要安排若干任务，每个任务有截止时间”，本质还是按右端点排序；另一种是把股票差分变成“你只能持有最多k股”，本质还是分段取正收益。

周赛题还有一个常见迷惑项，就是故意在数据范围上诱导你写动态规划。比如数组长度给到10的5次方，动态规划O(n²)必然超时，这时候贪心基本是唯一出路。反过来，如果数据范围不大，你要警惕这题可能故意让贪心失效，需要动态规划。范围本身不会告诉你答案，但能帮你快速筛掉一部分不合理的猜想。

4.3 面试现场讲贪心的三句话和边界控制

真实面试里，贪心题比动态规划题更容易被追问，因为代码太短，面试官只能从你的思路和证明过程里判断你是不是真会。我习惯用三句话打头阵：第一句，“这道题我想用贪心，策略是……”，直接亮出方案；第二句，“我构造过反例，比如……”，主动展示你的怀疑过程；第三句，“这个策略的正确性可以用交换论证法/数学归纳法证明”，把证明思路讲出来。

代码实现阶段，我最关注的是边界条件。贪心题代码短，但边界错一个字符就可能前功尽弃：跳跃游戏里的i > reach条件、跳跃游戏II里的range(n - 1)、无重叠区间排序后的空数组判断、柠檬水找零里5美元计数器归零的判断，都是高频翻车点。写完后我会手动跑三个特例：空数组、只有单个元素、极端值（比如跳跃游戏里所有值都是1）。这三个特例能挡住90%的边界错误。

5. 常见误区与避坑心得：从假贪心到真二分

5.1 三个经典反例：贪心失效的边界

刷贪心题最大的坑不是不会写，而是“什么都想用贪心”。我整理三个最经典的反例，每一个都能让你对贪心的边界有新的认识。第一个是带权重的活动选择：活动加上权重之后，按结束时间排序的贪心策略就不再最优，因为一个时间短但权重低的活动可能挡住一个时间长但权重高的活动，你必须用动态规划。第二个是非标准面额找零：假设纸币面额只有1、5、11，要凑15，贪心会先拿11，然后需要1+1+1+1，一共5枚；但5+5+5只要3枚，贪心当场失败。这个例子说明了局部最优（优先拿最大面额）并不等于全局最优。

第三个是0-1背包：如果物品可以分割，按单位价值排序贪心是对的；但每个物品只能整件拿走时，贪心就会失效，因为“拿一个高性价比大件”可能塞不下，而“换几个小件”反而能塞满背包。这三个反例告诉你一个共同规律：贪心失效的根源都在于“局部选择会改变后续可选项的集合”。一旦出现这种耦合，就要考虑动态规划或搜索了。

提示：遇到一个想用贪心的问题，先花两分钟尝试构造反例。构造不出来，再谈证明；构造得出来，直接转向其他算法。这两分钟往往会帮你省下几小时的错误方向。

5.2 爱吃香蕉的狒狒：贪心还是二分答案

Hot 100相关讨论里经常被问到“073爱吃香蕉的狒狒”，也就是LeetCode上那个狒狒吃香蕉的题：N堆香蕉，每小时最多吃某一堆里的k根，如果这堆少于k根，吃完后这一小时剩余时间就歇着，求能在H小时内吃完所有香蕉的最小k。很多人第一反应是“吃得越快越好”，试图用贪心推k，但这题恰恰不是贪心，而是二分答案。

原因很简单：这里不是“选什么顺序吃”的问题，而是“给定一个k，能不能在H小时内吃完”的可判定问题。每个k对应一个结果，k越大越快吃完，这个单调性让二分成立。check函数就是遍历所有香蕉堆，把每堆需要的小时数累加，向上取整，判断总小时数是否不超过H。代码很短，但思路和贪心完全不同。

def minEatingSpeed(piles, h): def can_finish(k): return sum((p + k - 1) // k for p in piles) <= h lo, hi = 1, max(piles) while lo < hi: mid = (lo + hi) // 2 if can_finish(mid): hi = mid else: lo = mid + 1 return lo

区分贪心和二分答案，我总结了两个信号：贪心问的是“按什么顺序安排这些选择”，二分答案问的是“这个参数取多少能满足条件”。前者需要证明局部最优能导出全局最优，后者只需要验证单调性。

5.3 刷题顺序与复盘方法

Hot 100贪心这部分，我建议按入门到进阶的顺序刷：先做455分发饼干和860柠檬水找零，这两道帮你建立“局部最优”的直觉；再做763划分字母区间和435无重叠区间，掌握区间排序；然后上55、45、122、134这一组序列贪心，感受“维护边界”和“差分累加”的思维方式；最后刷406根据身高重建队列，体会排序规则设计对贪心的重要性。

每道题做完，我建议你顺手写一个五行的复盘笔记：题目是什么、贪心策略是什么、一句话证明思路是什么、时间空间复杂度是多少、你的代码在哪个边界上差点出错。这个模板看起来很笨，但刷完这十几道题你回头看，会发现它们之间的共性比你想象中大得多，复盘笔记能帮你在周赛里快速完成模式匹配。

我个人做Hot 100贪心这部分时，最大的体会是：贪心题的代码长度和思维成本完全不成正比，代码越短，越要警惕“我是不是碰巧过了”。所以每道题我都强迫自己补一句证明，哪怕是口头复述。这样坚持下来，后来遇到周赛里的包装题，我第一反应不再是“这题我好像见过”，而是“这个局部选择会不会让后面的选择变差”——这比记住一百道题更重要。