力扣算法刷题到了 Day 34，今天跟第一周的状态完全不一样。刚开始刷力扣，我恨不得一天干完五六道简单题，觉得AC数量越多越有成就感；到了第三十多天，反而开始主动降速，一道题做完还要追问一句“如果数据再大一个量级，这个解法还成立吗”。这种转变不是突然来的，是被几道卡了很久的中等题给逼出来的。
Day 34这一天的计划，我原本想继续跟着力扣热题100的列表往后刷，结果发现已经连续好几天在东一榔头西一棒子地做题，今天干脆给自己定了一个小专题：贪心算法。不是说搜索热词里出现“贪心算法”就一定要刷，而是这个知识点跟排序、二分、动态规划的关系太紧密了，尤其是做区间类题目时，光靠暴力枚举会让运行时间变得惨不忍睹。这篇文章就把今天的完整刷题过程记录下来，包括题单选择逻辑、每道题的思考链路、翻车现场和排查心得，希望能给同样在力扣刷题路上推进的读者一点参考。
1. 第34天规划思路：为什么把贪心单独拎出来练
1.1 贪心算法到底在解决什么问题
很多刚接触算法的朋友一听到“贪心算法”就紧张，觉得它像玄学，一会儿对一会儿错。实际上，贪心算法的核心只有一句话：在每一步都做出当前看起来最优的选择，期望最后拿到全局最优解。它跟动态规划的区别在于，动态规划会记录所有可能的状态，通过状态转移逐步推导；贪心则不管未来的变化，只凭当下条件做决定。
这个思路放到生活里特别好理解。比如我周末要在家做四道菜，每道菜的耗时不同，但只有一口锅，怎么安排顺序能让最后一盘菜最早端上桌？最省事的贪心策略就是“耗时短的先做”，因为这样锅的空闲时间最少。放到算法题里，类似的逻辑就是排序后逐个处理。不过贪心不是万能的，很多题目靠贪心做出来是错的，Day 34之所以专门练它，就是想通过大量题目把“能贪”和“不能贪”的边界摸清楚。
Day 34我还特意把排序算法复习了一遍。因为大多数贪心题都需要先排序，尤其区间类问题，不排序根本没法谈贪心。每天刷题如果只盯着题解看，很容易忽略这个前置条件，导致代码逻辑全对，样例就是过不了。
1.2 今日题单是怎么筛出来的
今天的题单我没有随便从题库热榜里点，而是按“区间问题 + 跳跃类问题 + 分配类问题”三个方向来挑。选择逻辑是参考力扣刷题攻略里常说的一个经验：贪心最经典的题型就那么几种，与其贪多嚼不烂，不如把一个类型吃透。
我选了这三道作为今天的核心：
- 跳跃游戏 II：贪心 + BFS思维，重点练“最远可达距离”这个状态变量。
- 合并区间：排序 + 数组维护，练的是区间端点合并技巧，力扣热题100的常客。
- 会议室 II：排序 + 最小堆，练的是“重叠区间需要多少资源”这一类问题，属于合并区间的进阶版。
选完这三道，我又从力扣hot100里翻到几道备选题，像分发饼干、无重叠区间、用最少数量的箭引爆气球。如果前面的题AC得很顺，还可以顺手加一道。这样安排的好处是，每个题目之间都有递进关系，第一道题理解“向右最远能跳多远”，第二道题理解“两个区间怎么合并”，第三道题理解“多个重叠区间怎么动态安排资源”，知识点是一层层叠上去的，而不是像无头苍蝇一样乱撞。
1.3 一天的节奏安排
我习惯把刷题时间放在晚上，两三个小时整块时间，中间不切出去看短视频。Day 34的节奏是：
- 前20分钟先复习昨天的错题，尤其是二分查找算法里几个边界条件。
- 然后进入今天的贪心专题，每道题先自己思考15到20分钟，不急着写代码。
- 如果卡住了，就翻开题解的提示部分，不看完整代码，然后自己重新写。
- 全部AC之后统一总结，把每道题的核心思路用一两句话写进自己的错题本。
这样的节奏看起来“慢”，实际上比一晚上做八道题要扎实得多。刷题最怕的是看过题解之后觉得自己会了，关上页面两手一摊，第二天再见面完全是陌生人。
2. 三道典型题的拆解与实现
2.1 跳跃游戏 II：用最少的步数到达终点
跳跃游戏 II的题意很直观：给一个非负整数数组，每个元素表示你在当前位置最多能往后跳多远，问最少跳几次能从第一个位置跳到最后一个位置。第一眼看上去很像广度优先搜索，每一层是当前步数能到达的所有位置，步数加1层数就变深一层，答案就是最早到达终点的层数。这么想没有错，但如果真用BFS去模拟，复杂度会很高。
这里贪心就能派上用场。我习惯维护两个变量：当前步数能到达的最远边界cur_end，以及下一步能到达的最远边界farthest。从头遍历每个位置，不断用当前位置能跳到的范围更新farthest；当遍历到cur_end时，说明这一步已经走到了极限，必须再跳一次，于是步数加1，cur_end更新为farthest。整个过程只需要一次遍历。
核心代码是这段：
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我第一次写的时候有个误区，喜欢在循环里比较farthest和n-1，结果发现有些情况下提前break会漏算。其实只要把循环范围限定到n-2，到达最后一个位置之前，每一步都能被正确统计。这道题也让我想起另一个常见变体“跳跃游戏 I”，它只问你能否到达终点，贪心思路更简单，只用维护farthest并判断是否小于当前位置即可。如果把这两道题放一起做，对“最远可达距离”的理解会深很多。
2.2 合并区间：先排序再贪心
合并区间这道题，从力扣热题100到各家公司面试算法题里都频繁出现。题目说得很清楚：给你一堆区间，把有重叠的合并成一个，最后返回不重叠的区间列表。我第一次做的时候很天真，直接在原数组上不断找重叠区间合并，结果代码写得非常丑，还要套两层循环。后来看题解才知道，这类区间题第一步永远是排序。
按区间起点排序之后，问题变得异常干净。我们维护结果列表中的最后一个区间，然后遍历每个新区间。如果新区间的起点大于当前合并区间的终点，说明它们不重叠，直接加入结果列表；否则就说明有重叠，需要把当前合并区间的终点更新为两者终点的较大值。
代码长这样：
def merge(intervals): if not intervals: return [] intervals.sort(key=lambda x: x[0]) res = [] for start, end in intervals: if not res or start > res[-1][1]: res.append([start, end]) else: res[-1][1] = max(res[-1][1], end) return res这里有一个非常容易被小看的细节：排序时到底按左端点还是右端点？今天我把两种写法都试了一遍。按左端点排序简洁直观，按右端点排序在某些特殊场景下也可以，但合并时处理起来更绕。所以我的建议很简单，这类题一律按左端点升序。还有就是要小心“相等”的情况，比如当前区间的start等于res[-1][1]，严格来说它们是可以合并的，因为区间是连续的，不算重叠，但按重叠处理也不会错。这个边界条件值得多在本地跑几遍，才能形成肌肉记忆。
2.3 会议室 II：区间重叠的进阶玩法
会议室 II是很多算法练习平台上的经典面试题，题意是你有一堆会议的起始时间，问至少需要多少个会议室。跟合并区间不同，这里关心的不是把区间合并掉，而是同一时刻最多有多少个会议在同时进行。可以把它理解成一个峰值问题：在时间轴上画线段，每到一个开始时间点+1，每到一个结束时间点-1，最大前缀和就是答案。
更常见的解法是排序加最小堆。先把会议按开始时间排序，然后用一个小顶堆保存当前正在开会的会议结束时间。遍历每个会议时，先看堆顶的结束时间是不是早于当前会议的开始时间，如果是，说明那个会议已经开完了，可以把这个会议室腾出来，就弹出堆顶；然后把当前会议的结束时间压入堆中。最终的堆大小就是需要的会议室数量。
import heapq def min_meeting_rooms(intervals): if not intervals: return 0 intervals.sort(key=lambda x: x[0]) heap = [] for start, end in intervals: if heap and heap[0] <= start: heapq.heappop(heap) heapq.heappush(heap, end) return len(heap)这道题最妙的地方在于，它把贪心和堆数据结构结合到了一起。贪心体现在“哪个会议最先结束，就优先复用它的会议室”，堆则是高效维护这个优先级的工具。如果只用数组模拟，每次都要扫描所有会议室找最早结束的，复杂度会变成O(n^2)，对大数据量直接卡死。类似的思想还可以用在“雇佣工人最短时间”“课程安排”等题目中，属于刷一遍能抵好几遍的那种题。
3. 贪心算法的通用套路和判断方法
3.1 什么时候能用贪心：局部最优是否等于全局最优
这是贪心算法最核心的思辨题。做题做多了你会发现，贪心题往往长得很像动态规划题，你完全能列出状态转移方程，但最后发现一股脑地选局部最优也能过。区别在于，动态规划是在一堆方案里做筛选，贪心只是其中一种特殊策略，它要求你证明“每一步选择当前最优，最终结果不会变差”。
我自己的判断方法是问三个问题：
- 这个问题有没有可证明的“排序规则”？比如合并区间按起点排，跳跃游戏按可达距离排。
- 做出一次选择后，问题的规模是不是能明显缩小？贪心通常是一种“走一步看一步”的缩减策略。
- 是否存在反例让贪心失效？如果能在脑子里构造出反例，那多半要用动态规划或者二分答案。
面对力扣上的区间重叠问题，还可以多看一眼题目数据范围。如果n只有10左右，可能暴力枚举就够；如果n到10^5，贪心加排序基本就是标准答案；如果还涉及最大化最小值之类的字眼，大概率不是贪心，而是二分查找算法配合贪心检验函数。
3.2 贪心、动态规划、二分查找怎么选
很多读者卡在不知道该用哪种思路，尤其是贪心和动态规划之间的界限。我打一个在力扣刷题攻略里看过的比方：动态规划像走迷宫，你把所有岔路口都记在本子上，最后从终点倒推哪条路最近；贪心像在迷宫入口遇到一个指南针，每次只朝着看起来最近的方向走，也不管后面会不会是死胡同。
具体到题目里，如果状态转移时每一步要做多个选择，而且选择之间有后效性，那大概率是动态规划；如果选择之后剩下的问题从结构上跟原问题一样，而且单调性明显，就可以试试贪心。比如经典的“零钱兑换”，求最少硬币数量，因为硬币面额之间有复杂组合，简单贪心是错的，必须用动态规划；而“用最少数量的箭引爆气球”这类区间问题，贪心就是标准解。至于二分查找算法，它经常和贪心组合出现，用来解决“最小化最大值”或“最大化最小值”的题目，这类题贪心只负责检验某个答案是否可行，二分负责缩小区间，Day 34我虽然没专门做，但思路上已经准备在后续专门开一天练。
3.3 证明思路：交换论证法
学贪心的时候，很多参考资料会提到交换论证法，听起来很吓人，其实逻辑很简单。假设你的贪心策略得到的最优解跟标准最优解不一样，试着交换其中两个相邻元素的顺序，如果交换后结果不会变差，就说明贪心选择可以替换为标准最优解的一部分。
以会议室 II为例，为什么每次都复用最早结束的会议室是最优的？因为从全局看，一个会议室空着也是空着，能塞进一个“结束早”的会议，永远比塞进一个“结束晚”的会议更灵活。万一后面有一个特别紧急的会议要在这个时间点开，先结束的会议室已经空出来了，而晚结束的会议室还占着位置，区别就在这里体现出来。
老实说，正式面试的时候很少会要求你写完整数学证明，但脑子里有这个意识很重要。很多题你判断不了能不能用贪心，其实就是因为缺少这种“尝试交换”的训练。我建议每天刷题时选一道题，专门在草稿纸上写下“为什么这个贪心是对的”，哪怕写得很粗糙，也比稀里糊涂AC十道题强。
4. 刷题过程中的坑与排查经验
4.1 排序条件写错导致连环崩
今天在合并区间这道题上，我故意试了一个反例来验证排序规则的重要性：区间是[[1, 9], [2, 5], [6, 8]]，如果按右端点排序，遍历时会先处理[2,5]再处理[6,8]，看起来没问题；但如果区间换成[[1, 4], [2, 3], [5, 8]]，按右端点排序后变成[[2, 3], [1, 4], [5, 8]]，处理[1,4]时需要和res最后一个区间[2,3]合并，结果没问题，可一旦出现[2, 2]这种单点区间，情况就乱套了。
所以我的第一教训是：先想清楚“排序后要借助什么顺序做贪心”，再动手写排序key，不要无脑 sort。尤其是区间重叠类题目，按左端点升序是默认操作，除非题目明确要求按右端点处理。
4.2 边界值和极端情况的处理
很多算法错误不是出在核心逻辑，而是出在空数组、单元素数组、数值相等这些边界情况。跳跃游戏 II里如果数组长度是1，答案直接是0，不需要进入循环；会议室 II里intervals为空时堆操作会出问题，必须先判空。
更隐蔽的坑是整数溢出。力扣某些题的坐标范围很大，如果用int存“起始点+跳跃距离”可能会越界，特别在C++、Java这类语言里要格外小心。今天我在本地跑测试用例时，专门加上了一组极端值，比如nums里的元素接近int最大值，确认计算结果还在安全范围内，才把答案提交。别看这些细节不起眼，很多真实项目的生产环境崩溃，根因就是边界值没处理好。
4.3 复杂度分析与超时问题
今天的三道题都是O(n log n)或者O(n)级别。会议室II因为要维护堆，复杂度是O(n log n)，合并区间和跳跃游戏II都是O(n)，前提是跳跃游戏II不额外创建队列。如果在跳跃游戏II里真写BFS，每个位置都可能被扩展多次，最坏情况会退化到O(n^2)，力扣数据量一大就会超时。
我试着写了一个朴素BFS版本做对比，用的还是deque，mark数组标记已经访问过的位置，数据量到10^5时明显卡顿。这个对比实验让我深刻理解了为什么很多题解会强调“用BFS思想理解，但实现用贪心”，看别人的分析是一回事，自己把两种写法都跑一遍，性能差异才能变成真正的体感。
4.4 常见问题速查表
今天踩坑之后，我把贪心类题目的常见问题整理成了一个小表，以后遇到同类问题直接翻：
- 问题：排序规则不确定；排查方向：观察是否区间类问题，优先按起点升序，特殊场景考虑终点降序。
- 问题：感觉是DP但想不出状态转移；排查方向：先尝试按某个维度排序，再判断局部选择是否能组成全局解。
- 问题：答案偏大或偏小；排查方向：检查边界条件，尤其是相等值，重叠区间和端点相连接的区别。
- 问题：超时；排查方向：数据结构降级，例如把数组扫描换成堆、双指针、二分查找算法。
- 问题：无法证明贪心正确；排查方向：构造极端反例，或者改用动态规划/记忆化搜索兜底。
5. Day 34之后的刷题攻略与复习建议
5.1 如何按专题推进力扣热题100
力扣热题100是非常好的一份题单，但直接按顺序刷效率不高。我的经验是把题单重新按知识点打散，抽出数组、链表、二叉树、回溯、动态规划、贪心、二分、图论这些大块，然后每周盯住一个专题来刷。比如Day 34开始练贪心，接下来几天就应该连续刷无重叠区间、用最少数量的箭引爆气球、分发饼干、跳跃游戏I和II、加油站、监控二叉树，把这些题放在一起对比，理解每种变体之间微小差异在哪里。
贪心专题结束之后，再进入二分查找算法专题时，你会发现自己对“单调性”的感知变强了。很多二分题其实都藏着贪心的影子，比如“每个学生分到的书页最大值”这类题目，先用二分枚举答案，再写一个贪心检查函数判断是否可行。这种跨专题的联动，才是刷题量积累到一定程度后的真正回报。
5.2 错题本和“再AC一遍”机制
我比较推荐建立一个错题本，但不要抄题目和代码，而是记录三个东西：第一，我最初的错误思路是什么；第二，正确思路的关键转折点在哪里；第三，这个题目属于哪个专题，可以跟哪些题归为一类。Day 34的错题本里，我写下了“跳跃游戏II第一版代码在n=2时多算了1步”，以及“会议室II的heap弹出条件应该是<=而不是<”，这些信息很短，但复习时极其管用。
“再AC一遍”是我自己给自己定的规矩：一道题AC后，隔一周重新做一次，不看题解，不看自己原先的代码，白纸一张重新写。如果能够在10到15分钟内做出来，才算真正掌握。Day 34的三道题，我计划在下一周之后重新做一遍，到时候如果又能写出不同思路，比如不用堆而用差分数组完成会议室II，那说明理解又上了一个台阶。
5.3 给不同基础读者的建议
如果你是刚开始刷力扣的小白，我不建议一上来就复刻Day 34这种专项目，应该先刷数组和字符串类型的简单题，把语言基础API搞熟，比如Python的切片、列表推导式、sort的key写法，再逐步过渡到双指针、哈希表。贪心算法本身不难，但前提是你对排序、堆这些工具有一定的熟悉度，否则很容易被工具细节干扰。
如果你已经刷了一百道左右的中等题，可以像我今天这样把某个专题单独抽出来集中练，一次练三到五道同类型题目，把它们的共性提炼出来。贪心题很多时候是在考察“你能不能把问题转化成一个排序后的线性扫描”，一旦你习惯了这种视角，很多所谓hard题也就变成了中等题。
数据结构与算法这条路没有捷径，但一定有更省力的走法。我最反感把刷题等同于“背题”，因为面试题和真实工程里的问题永远在变化，背下来的解法根本套不上去。真正有效的是积累一套自己的分析流程：看到题目先观察数据范围和问题特征，再猜测可能的知识点，接着通过用例验证，最后写代码和总结。
Day 34结束后，我坐在电脑前想了一个很有趣的问题：如果跳跃游戏II的数组里允许负数，也就是可以向左跳，这个问题会变成什么样？答案是它会变成一个更复杂的图论最短路问题，贪心就失效了，需要用BFS或者Dijkstra来做。这就是刷题最迷人的地方，一个条件的改动会彻底改变题目本质，而你能做的，就是把每个边界都摸透。
今天我个人最想分享的小技巧是：每道题AC之后，试着改一改题目条件，比如把“最少跳跃步数”改成“最多能跳到的位置数量”，或者把“合并重叠区间”改成“合并所有有交集的区间”。这种变体练习花不了多少时间，但对巩固贪心思路特别有帮助。我已经把它列成Day 35的固定热身动作了。
