第73天算法刷题复盘：二分查找、贪心、堆与排序模块化实战

1. 第73天我决定把刷题节奏重新按“模块”切一遍刷到第73天这个节点说实话心态和前几天完全不一样。前30天是硬扛靠新鲜感撑着一天三题不写出来不睡觉40到60天开始进入一种机械状态题目刷得挺多但回头一看脑子里是一团浆糊二分查找的边界还是每次都要想半天贪心的证明还是每次都要重新推。到第73天我做了个决定不再按题号顺序往前冲而是把当天的算法刷题任务拆成“主题模块”一天只啃一个方向配套做2到3道题加1道重写把数据结构与算法的基本功重新夯一遍。具体到这一天我给自己定的主题是“查找与选择的效率问题”围绕二分查找、贪心、堆这三块展开。为什么挑这三个因为它们有一个共同点都不是靠复杂数据结构堆出来的而是靠思路上的收敛。二分是靠把搜索空间砍半贪心是靠每一步选局部最优堆是靠只维护“当前最该被关注的那批元素”。这三样东西在面试里出现频率高得离谱实际写业务代码的时候也经常用得上比如在大量数据里找TopK、在有序区间里定位、在资源分配里做取舍绕不开它们。这篇文章我打算把当天刷的题、写过的代码、踩过的坑、以及我自己总结出来的一些非教科书经验完整记下来。适合的人群很明确正在刷题、刷了但没什么体系感、或者刷到一半开始怀疑自己方法不对的人。如果你也卡在“题做了不少但一换题型就懵”的阶段那这一天的记录应该能给你一点参考。写代码的语言统一用C因为刷题场景下它对时间复杂度的控制最直观容器和算法库也够用。2. 当天任务清单与选题思路拆解先把我第73天的实际安排摊开讲避免写成空泛的方法论。当天总共三个小时分成了热身、主攻、复盘三段。热身30分钟是重写昨天没写顺的一道题主攻两小时是当天的新题剩下半小时用来把当天的代码整理成笔记并手推一遍关键复杂度。这个时间盒是我在刷到第50天左右才稳定下来的之前经常一坐四五个小时效率反而低。2.1 为什么第73天要回到“二分、贪心、堆”这三个老面孔很多人刷到中期会有一种心理简单的题不想写觉得浪费时间专挑难题。我前两个月也犯过这个毛病结果就是简单题的正确率反而不稳。二分的边界写错、贪心漏掉最后一个区间、堆的大小关系搞反这些都是“太熟了所以不看”造成的错误。所以第73天我刻意回到这三块而且要求自己不看模板、从零推导写完再去对照标准写法。提示模块化刷题时一天一个主题的收益远大于按题号顺序刷。原因是同类题的解题模式相同连续做能在短时间内形成条件反射而不是每次都要重新切换思维模式。选题上我一共动了四道题一道经典二分变形找左边界、一道跳跃游戏II贪心、一道数据流中的第K大元素堆、外加把昨天的归并排序手写重写一遍。四道题加起来覆盖了查找、贪心、堆、排序四个高频考点而且它们的代码量都不大适合在有限时间里吃透而不是囫囵吞枣。2.2 时间盒分配与难度梯度的对照我把当天的安排整理成了一张表方便你直接照搬这种节奏。核心原则是“先热身找手感再上强度最后收尾复盘”每一段都有明确产出而不是刷完就过。阶段时长内容产出物热身30分钟重写昨日归并排序一份能默写出来的模板主攻一40分钟二分查找左边界变形代码边界推导手稿主攻二40分钟跳跃游戏II两种解法对比主攻三30分钟数据流第K大元素堆实现复杂度分析复盘30分钟整理笔记、手推复杂度当天笔记归档这张表看起来简单但它解决了一个很实际的问题刷题最容易失控的地方就是时间。没有时间盒一道题卡住能耗两个小时最后当天计划全废。设了时间盒之后卡住超过15分钟就去看题解看完合上题解自己重写一遍效率反而更高。我自己实测下来一天三题加复盘比一天五题不加复盘的效果要好因为复盘那半小时才是真正把题目变成自己东西的环节。3. 二分查找把边界问题写成肌肉记忆二分查找这四个字每个学过数据结构与算法的人都会写但真正能在各种变形题里不出错的人不多。当天我刷的是一道“在有序数组中找目标值的第一个出现位置”标准二分的直接变形但边界稍微不注意就会返回错误的索引。这一节我把当天推过的三种写法完整记下来重点落在“为什么这样写”而不是“抄这个模板”。3.1 左闭右闭与左闭右开到底该选哪一种二分的区间定义有两大流派左闭右闭[left, right]和左闭右开[left, right)。很多题解只给代码不讲选择理由导致初学者两套混着用于是各种差一错误。我的结论是先选一套然后所有变形题都用这一套改不要两套来回切。当天我是用左闭右闭写的因为它和数组下标天然一致写循环条件left right时不容易忘掉等号。// 左闭右闭在有序数组 nums 中找 target 的第一个位置 int lowerBound(vectorint nums, int target) { int left 0, right (int)nums.size() - 1, ans -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { // mid 可能是答案记录后继续往左找 if (nums[mid] target) ans mid; right mid - 1; } else { left mid 1; } } return ans; }这段代码里最关键的是right mid - 1和left mid 1这两个动作。它们保证了每次循环区间都在严格收缩不会出现 left 和 right 卡住不动的情况。而mid用left (right - left) / 2而不是(left right) / 2是为了防止两数相加溢出。这个细节在题目数据量小的时候看不出差别但一旦数组长度接近整型上限left right就会翻成负数直接死循环或者越界。3.2 三个必须手算的点少一个都可能死循环写完代码之后我养成了一个习惯拿长度为1、2、3的数组各手推一遍。这三个规模能覆盖绝大多数边界问题。具体来说我会检查三件事。循环终止条件与区间定义是否匹配。用左闭右闭就必须是left right因为区间非空时左右端点可能相等用左闭右开就必须是left right。这两个写反要么漏掉一个元素要么多跑一轮。收敛动作有没有漏掉端点排除。找左边界时命中目标后要把 right 往左压也就是right mid - 1而不是right mid。写成后者在长度2的数组里会原地打转。返回值语义是否和调用方约定一致。返回索引还是插入位置找不到时返回 -1 还是 left这个一定要在函数注释里写死否则换个题就容易脑补错。注意二分的bug有个特点小数据能过大数据才崩。我当天的做法是每写完一道二分题先用自己构造的 {1}、{1,2}、{1,1,2} 这几个小数组跑一遍再看题解的测试用例。花两分钟能省掉半小时的调试。当天推完之后我把这套检查动作写进了笔记之后再做二分题几乎不再出错。总结下来二分真正难的从来不是“折半”这个想法而是每一轮边界的取舍。把取舍的规则固定下来变成条件反射这一块就算过关了。4. 跳跃游戏II贪心算法的两种视角从容易想到到足够快跳跃游戏II是当天主攻里最有意思的一道。题目大意是给你一个非负整数数组每个位置的数字表示你在这里最多能往前跳的步数问从第一个位置跳到最后一个位置最少需要几步。这道题是贪心算法的经典应用但它有两层台阶第一层是“能想到”第二层是“想到O(n)的写法”。很多人停在第一层能用但会被判定超时能爬到第二层才算真正理解贪心的本质。4.1 反向查找最容易想但代价最高我第一反应是反向贪心从最后一个位置往前推每次都找最靠左的、能一步跳到当前位置的位置把它作为新的目标直到回到起点。这个思路的直觉很强——要让总步数最少最后一步当然希望从尽可能靠前的位置起跳这样前面需要覆盖的距离就更短。代码写出来大概是下面这样。int jumpReverse(vectorint nums) { int pos nums.size() - 1, steps 0; while (pos 0) { for (int i 0; i pos; i) { if (i nums[i] pos) { // 从 i 能一步到 pos pos i; steps; break; } } } return steps; }这个写法正确但复杂度是 O(n²)。因为每确定一个目标位置都要从头扫描一遍数组。数据规模上万之后就会明显变慢。我当天先写了它跑了一遍测试确认思路对然后才去想怎么优化。这个顺序很重要先把正确性拿到手再谈效率而不是一上来就追求最优解导致思路卡死。4.2 正向贪心一次遍历拿到 O(n) 的解优化后的写法是正向扫描维护一个“当前这一步能覆盖到的最远位置”和“当前这一步的边界”。思路是在到达当前边界之前不断更新下一步能跳到的最远距离一旦走到了当前边界说明这一步用完了步数加一把边界推到最远距离。整个过程只遍历一次数组。int jump(vectorint nums) { int n nums.size(); int end 0; // 当前这一步的边界 int farthest 0; // 下一步能到的最远位置 int steps 0; for (int i 0; i n - 1; i) { // 注意是 n-1最后一个位置不用再起跳 farthest max(farthest, i nums[i]); if (i end) { // 走到边界必须跳一次 end farthest; steps; } } return steps; }这里有两个容易写错的地方。第一循环条件是i n - 1而不是i n因为到达最后一个位置之后就不需要再跳了多扫一轮会让步数多出一。第二if (i end)这个判断要在更新 farthest 之后顺序反了就会少算一步。当天我就因为把这两句调换位置在样例 {2,3,1,1,4} 上得出了错误答案排查了十几分钟。提示贪心题最怕的就是“看着对但没证明”。我的做法是每写一道贪心都用最朴素的动态规划或暴力解法对拍一组小数据。跳跃游戏II用记忆化搜索做对拍很简单跑几十组随机数据一致了才敢说自己的贪心是对的。两种写法的复杂度差距很明显反向是 O(n²)正向是 O(n)。在数据量十万级别时前者可能要跑几秒后者毫秒级出结果。这道题也让我更理解贪心的一个套路——能正向贪就不要反向贪因为正向扫描通常能边遍历边维护状态天然做到一次遍历。5. 堆的实际用法别急着排序先维护一个大小为K的堆当天第三道题是“数据流中的第K大元素”要求设计一个结构能不断添加数字并随时返回当前第K大的元素。这类题如果每次查询都排序复杂度是 O(n log n)查询频繁时完全扛不住。正确姿势是用一个大小为K的小顶堆堆顶就是第K大的元素。5.1 为什么是小顶堆而不是大顶堆第一次接触这个题的人几乎都会想反求第K大直觉上用大顶堆。但仔细想一下——大顶堆的堆顶是最大值维护它只能让你随时拿到第一大的元素想知道第K大就得弹出K-1次查询一次就 O(K log n)。而小顶堆不同我们只保留K个元素堆顶是这K个里最小的也就是整个数据流中的第K大。多进来的元素如果比堆顶小它连前K都进不了直接丢掉比堆顶大就替换堆顶。整个过程逻辑特别顺。class KthLargest { priority_queueint, vectorint, greaterint pq; // 小顶堆 int k; public: KthLargest(int k, vectorint nums) : k(k) { for (int x : nums) add(x); } int add(int val) { pq.push(val); if ((int)pq.size() k) pq.pop(); // 超出K就弹掉最小的 return pq.top(); // 堆顶即第K大 } };这段代码里greaterint是让优先队列变成小顶堆的关键。默认的priority_queueint是大顶堆很多人第一次写这个题就栽在这个默认行为上结果返回的一直是最大值怎么都对不上。5.2 海量数据TopK的参数估算堆的价值在大数据场景下才真正体现。假设有1亿个整数要取最大的100个直接全部排序需要把这些数据都装进内存时间和空间都吃不消。用小顶堆只需要维护100个元素的内存遍历一遍数据流即可空间从 O(n) 降到 O(K)。我当天还顺手算了一笔账假设每条记录占用8字节1亿条就是约800MB普通机器一次性加载会触发频繁的内存交换而维护一个K100的堆只占800字节几乎可以忽略。时间上每个元素进堆出堆是 O(log K)总体 O(n log K)比全排序的 O(n log n) 小一个量级。这也是为什么日志分析、排行榜这类场景几乎都用堆来做TopK而不是先排序再截取。注意堆的大小一定要卡死在K。我见过有人忘了在push后判断size堆越堆越大最后退化成全量排序等于白用。养成“push之后立刻检查并pop”的习惯能避免这个坑。堆这块还有个小技巧如果K接近数据总量比如取前90%那用小顶堆反而没优势直接排序更快。所以选不选堆要看K和n的比例。经验上K远小于n时才用堆否则排序更划算。6. 排序算法横向梳理归并为什么值得单独手写一遍当天热身的归并排序我特意花时间重写了一遍。原因很简单递归式的分治结构、跨区间合并时的指针操作、以及“临时数组”的写法都是面试里常考、日常也常被复用到的模式。把归并写熟等于顺便掌握了分治的骨架后面做逆序对、链表排序、区间统计这些题都能直接套。6.1 六种常见排序的对照表刷到第73天我越来越觉得排序算法不能只记名字得把它们的适用场景和取舍搞清楚。下面这张表是我当天整理的核心对照参数都按平均复杂度、最坏复杂度、空间、稳定性来列。算法平均时间最坏时间空间稳定适用场景冒泡排序O(n²)O(n²)O(1)是教学演示、近乎有序的小数组插入排序O(n²)O(n²)O(1)是数据量小、基本有序归并排序O(n log n)O(n log n)O(n)是需要稳定排序、外部排序、链式结构快速排序O(n log n)O(n²)O(log n)否内存中大规模随机数据堆排序O(n log n)O(n log n)O(1)否空间受限且要求最坏可控计数排序O(n k)O(n k)O(k)是整数且取值范围集中表格里最值得记住的一点是归并是稳定排序里唯一能保证 O(n log n) 最坏时间的。快速排序虽然平均更快但最坏情况会退化到 O(n²)堆排序稳定在 O(n log n) 但常数大、且不稳定。所以当题目明确要求稳定又对最坏时间有要求时归并就是首选。6.2 归并的两种写法与链表场景的差异数组上的归并我用得最多模板长这样void mergeSort(vectorint a, vectorint tmp, int l, int r) { if (l r) return; // 单元素天然有序 int mid l (r - l) / 2; mergeSort(a, tmp, l, mid); mergeSort(a, tmp, mid 1, r); int i l, j mid 1, k l; while (i mid j r) { tmp[k] (a[i] a[j]) ? a[i] : a[j]; // 保证稳定 } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int t l; t r; t) a[t] tmp[t]; // 拷回原数组 }有两处细节值得说。第一合并时的比较用了而不是这是保证稳定性的关键两者相等时优先取左半边的元素左半边的原始位置更靠前相对顺序就保住了。第二递归结束条件是l r用单元素作为最小有序区间。如果写成l r会对非法区间继续递归直接栈溢出。链表上的归并写起来不太一样因为它没法像数组那样用下标随机访问找中点得用快慢指针合并时是改指针而不是拷回数组。面试里“排序链表”这道题几乎是归并的专属场景因为快排无法高效地做随机访问。当天我把数组版写熟之后顺手在纸上推了一遍链表版快指针每次走两步慢指针每次走一步快指针到尾部时慢指针正好在中点然后断开、递归、合并。这个套路值得背下来。提示写归并时临时数组一定要在递归外部一次性分配好再传进去不要在每次递归里新建。递归里反复申请内存会让常数变得很大实测在十万级数据上差别能达到两三倍。7. 当天踩坑记录与问题排查速查表这一天下来四道题总共花了不到两个半小时但中间卡壳的地方不少。我把它们整理成排查表下次遇到类似症状可以直接对照。7.1 四个典型问题与定位思路第一个问题是二分查找返回了 null。排查后发现是循环条件写成了left right导致长度为1的数组根本没进循环。改成left right就好了。这类问题的通用定位方法是把区间长度等于1的情况单独拿出来在纸上跑一遍看进不进循环。第二个问题是跳跃游戏II步数多了一。原因是我用了i n的循环条件最后一步在终点又触发了一次边界判断。判断这类问题的办法是构造只含一个元素的数组最少步数应该是0如果算出来是1就说明多算了。第三个问题是堆的返回值总是最大值。这里纯粹是priority_queue默认大顶堆造成的加上greaterint就正常了。后来我总结写堆相关的题先确认“我要堆顶是最大还是最小”再决定加不加比较器能避免大部分逻辑反转。现象可能原因排查动作二分返回-1但答案存在循环条件或收敛动作不匹配用长度1、2的数组手推贪心步数偏多循环边界包含了终点检查是否用 n-1 作上界堆顶取值不对比较器方向写反确认小顶堆要加 greater归并结果乱序临时数组未拷回或比较符写反检查拷回循环和 程序死循环mid 收敛动作漏了端点排除确认每轮区间严格收缩第四个问题是归并结果局部乱序。原因是合并之后忘了把临时数组拷回原数组只排了临时数组。这个错误特别隐蔽因为小数组可能恰好看起来是对的大数组才露馅。解决办法就是在拷回之后加断点确认原数组每一段都已经是排好序的。7.2 我自己的三分钟检查清单刷题到第73天我形成了一个习惯每道题提交前花三分钟做一遍固定检查。这份清单不长但拦下来的错误比想象中多。空输入和单元素输入会不会崩这两个是最常见的边界。循环的终止条件和我对区间的定义对得上吗有没有整型溢出的风险尤其是取中点、累加、乘法的时候复杂度估算和我选的算法匹配吗数据规模会不会超时代码里的每一行我都能解释它在干什么吗有没有“照着模板抄但不知道为什么”的部分第三点尤其重要。C里int通常是32位两个接近上限的数相加就会溢出。二分取中点用left (right - left) / 2是标准规避写法累加求和时则要考虑换long long。这些细节在数据规模小的时候不显眼但在真实场景里经常是线上问题的来源。8. 刷到第73天我改掉的几个习惯这天的记录写到这里其实最想分享的不是某道题的解法而是几个我在刷题过程中慢慢改掉的习惯。第一个是“只刷不复习”。前两个月我追求每日题数刷完就过结果同一类题换个说法就认不出来。后来我把每天的最后一小时固定用来重写昨天的题覆盖到的知识点才真正留下来。第二个是“遇到卡壳死磕到底”。以前我认为看题解就是抄答案后来发现卡超过二十分钟纯粹是浪费时间。现在的做法是给自己设一个硬性上限十五分钟没思路就看题解但看完必须合上题解自己重写写不出来就说明没真懂。第三个是“只写代码不动手推复杂度和边界”。纸上推导这一步看着笨但它把很多隐藏的错误提前暴露出来比调试器还快。尤其二分、贪心、动态规划这几类题手推小样例几乎能拦住八成以上的边界错误。第四个是“贪多求全”。我曾经想一天覆盖四五个知识点结果每个都浅。现在一天只啃一个模块配套两三道题深挖一天下来感觉很踏实第二天也不会因为信息过载而疲惫。如果让我给一个具体的做法我会说先把当天要刷的题按主题归类给每道题设时间盒写完务必手推边界和复杂度最后花半小时把当天的收获写成一句话笔记。这套流程跑上一个月你会发现自己不再依赖记忆某个具体题解而是有了自己的一套分析路径。第73天对我来说是个小节点也是把刷题从“刷数量”切换到“刷质量”的转折点后面的路还长但方向比以前清楚多了。