从第一次看到“击败100%”这个绿得发亮的提示到后来把这件事当成写题解的日常中间隔着的不是运气而是一整套关于复杂度、数据结构和代码常数的思考方式。这篇小记就把我这一年多在LeetCode上从挣扎到稳定输出击败率的过程掰开揉碎聊聊那些起决定性作用的优化思路、踩坑经历和刷题节奏适合正在准备算法面试或想在竞赛上再进一步的朋友。1. 从“能过”到“击败100%”一场关于复杂度的自我较量1.1 为什么性能优化值得较劲从面试到实战的反馈很多人刷LeetCode的第一步是“把题解出来”但题解出来仅仅是起点。面试官不会只看你的代码是否通过用例他们更关心你能否把运行时间压下来、能否把空间占用讲清楚。我在面试中遇到过两次一模一样的场景我给出一个时间复杂度O(n^2)的解法面试官点点头说“请再优化一下”我改成O(n log n)后他会继续问“还有没有更好的”。这种步步紧逼的节奏其实就是LeetCode击败率比拼的缩影——当你习惯了在击败率榜单上往上爬你在面试时对优化命令的敏感度会明显高出一截。实测下来追求高击败率对实战代码的反馈也很直接。业务系统里偶尔会遇到数据量突然翻十倍的接口那些“能过但很慢”的写法往往会变成隐患。LeetCode上的击败率本质上是一种压力测试逼着你养成预估数据规模、提前设计边界的习惯。哪怕你以后不刷竞赛题这种思维惯性也会让代码的健壮性上一个台阶。1.2 LeetCode百分比背后的计算机制和你想的不一样先聊一个被很多人忽略的细节LeetCode统计的“击败100%”并不是绝对意义上的最优解它只代表你打败了当前提交记录中所有同语言版本的历史提交。这个百分比会随提交时间变化也会因为语言分组不同而不同。同一份代码今天提交可能是击败98%明天可能是击败99.9%偶尔还会因为评测机波动跌到95%以下。了解这个机制之后我就不再盲目追求“永远100%”。一次提交跑出100%当然值得记录但如果代码的复杂度本身已经达到理论下限哪怕这次只击败了80%我也认为这是合格线。真正值得关注的是时间复杂度的量级和常数因子。击败率的波动是随机的复杂度的优劣是确定的。记录时我会标注“本次击败100%”和“核心思路是O(n)”两个信息后者才是长期价值的锚点。2. 拆解三道典型题的优化路径从暴力解法到最小化计算2.1 “爱吃香蕉的狒狒”的定位与二分套路“爱吃香蕉的狒狒”是LeetCode 073那道经典的“Koko Eating Bananas”。题目本身不复杂狒狒要在h小时内吃完n堆香蕉求最小吃速k。最直白的暴力思路是从k1开始逐个尝试复杂度是O(max(piles) * n)遇到大数直接超时。我第一次做这道题时就是暴力试的结果边缘用例直接教做人。后来发现这道题的正解是二分查找吃速k因为“能在h小时内吃完”这个判断具备单调性k越大越容易完成。把判断函数封装好二分区间从1到max(piles)整体复杂度就降到了O(n log max(piles))。拿到这一层的优化之后击败率基本能到90%以上但想冲100%还得抠几个细节。比如在判断函数里对每堆香蕉计算所需时间时用(pile k - 1) / k代替pile / k 1的取整写法可以减少一次分支判断又比如把二分右边界直接设为max(piles)而不是题目给的10^9能明显缩小搜索范围。这些常数优化叠加起来击败率就能稳定站上99%。2.2 两数之和的进阶为什么暴力解法总是输两数之和是LeetCode的第一题绝大多数人的第一个AC都来自暴力双层循环时间复杂度O(n^2)。但当你提交时击败率往往只有5%到10%。原因很简单n较大时O(n^2)的增长过于陡峭评测数据里藏着超大用例。把暴力换成哈希表是一道分水岭。一遍遍历每遇到一个数就检查target - nums[i]是否已经在哈希表中这样把时间压到O(n)的同时空间也从O(1)升到O(n)。很多人到这里就满足了但击败100%还差一步——动态规划式的遍历顺序不要在遍历过程中先存全部数据再二次查找而是边查边存。这样不仅提前返回结果还能减少哈希表存量的体积常数因子更小。我在提交记录里见过一个更极端的写法用数组模拟哈希表而不是用Python的字典因为Python字典的哈希运算和扩容开销相对较大。但那个写法对数值范围有限制不一定普适。我的习惯是先用标准哈希表写出清晰版本再用数组模拟优化一版看两版击败率差异再决定用哪个进题解。2.3 动态规划题型的优化思维状态压缩与剪枝动态规划是很多人的痛点也是高击败率最容易拉开差距的题型。以背包类问题为例最经典的二维DP很容易写但空间复杂度是O(n * capacity)提交上去击败率常常徘徊在50%到70%。这时候用滚动数组把空间压到O(capacity)击败率就会立马上一个台阶因为LeetCode对内存的排名同样敏感。做一维优化时要特别注意遍历顺序。01背包必须从大到小遍历容量完全背包则要从小到大。这个顺序不是玄学而是为了避免状态被重复使用。我一开始总是记混后来用了一句口诀“01倒着走完全正着走。”到了区间DP和树形DP优化的重点则变成了剪枝和状态定义的精简。每次做状态转移时先问自己这个状态真有必要存在吗能不能合并能把维度降下去代码跑起来的时间往往也跟着降下去。3. 击败100%的实用方法论五步优化流程与常用技巧3.1 第一步先暴力再讨论复杂度不管是新题还是旧题我都会逼自己先写一版暴力解法哪怕提交后超时也没关系。原因有两点一是暴力解法能验证我对题意的理解是否正确避免在一开始就走偏方向二是暴力解法提供了正确性基准之后的优化版本可以拿它来对拍。很多刷题新手容易犯的毛病是上来就背模板直接套二分或动规结果连题意都理解错了。先暴力、再优化的顺序本质上是在“理解问题”和“优化解法”之间建立了一道安全网。实测下来这个习惯能让我的解题正确率提升至少两成。3.2 第二步确定瓶颈选对数据结构暴力解法跑完一遍接下来要分析时间消耗在哪个环节。如果是查找慢就考虑哈希表或二叉搜索树如果是排序慢就考虑计数排序或桶排序如果是重复计算就考虑动规或前缀和。这一步是最考察基本功的也是高击败率的核心分水岭。举例来说遇到区间求和问题暴力解法是每次循环累加复杂度O(n * q)。优化思路是先构建前缀和数组让区间求和达到O(1)整体复杂度降到O(n q)。这背后其实是“数据预处理”思想把重复计算提前做掉换取查询时的高效率。LeetCode上大量的中等题本质上就是在考你能否识别出这种“预处理为上”的数据结构选择。3.3 第三步利用边界条件剪枝很多题的输入范围里藏着“剪枝”的线索。比如数据范围是正整数就可以在遍历时跳过0和1如果题目保证数组有序就可以提前break如果目标函数有明显单调性就可以用双指针或二分縮小区间。我在做区间合并类题目时就经常用这个技巧先把区间按起点排序然后遍历时如果当前区间起点大于上一个区间的终点就不可能再产生重叠直接跳过内层循环。这样的剪枝往往能把平均复杂度从O(n^2)降到接近O(n log n)水平。剪枝不是玄学是对题目约束条件的深度挖掘写题解时把这一步写清楚读者会觉得你是真懂而不只是背答案。3.4 第四步善用位运算和内置函数位运算在特定题型里是提升性能的利器。比如集合表示、奇偶判断、交换变量、快速乘以2或除以2等。Python的整数位运算相当快我经常用x 1代替x % 2用x 1代替x // 2不仅省时间代码看起来也更专业。内置函数的上限也值得深挖。Python的bisect模块做二分查找比手写快很多heapq做堆操作比手写堆靠谱得多。很多人总觉得内置函数不够灵活但其实它们是用C语言实现的常数因子远小于你手写的Python循环。在复杂度相同的情况下选用内置函数往往是击败率拉开差距的关键。3.5 第五步严谨测试与基准对比写完一版优化解法后不要急着提交先在本地用几个典型用例做基准测试。小数据用例检查正确性大数据用例检查运行时间和内存。如果时间在合理范围内再提交到LeetCode看击败率。我常用的做法是写一个生成随机数据的脚本对暴力解法和优化解法做对拍跑几百组用例确保结果一致。这样提交时的信心会足很多也能避免因边界用例考虑不周导致重新提交的尴尬。对LeetCode的评测机制比较熟悉之后还可以根据题目数据范围预判用例强度从而决定是否值得继续抠常数。4. 刷题进阶中的反面教材我踩过的那些坑4.1 盲目追求一行代码的代价有一段时间我特别喜欢把题解压成一行Python表达式觉得这样很酷还特意去学各种列表推导式的嵌套和any()、all()的花式用法。虽然有的题确实能压成一行且击败率不低但遇到逻辑稍微复杂的题目时这种写法极大降低了可读性面试时如果照着读给你对面的工程师听对方大概率会皱眉。有个血的教训一次周赛里我为了方便炫技用嵌套推导式写了一版解法结果调试时根本看不出来哪一步逻辑错了最后提交失败。从那以后我给自己定下规矩“先可读后紧凑。”如果一行代码能在不影响性能的前提下保持语义清晰可以用如果牺牲了可读性坚决不干。毕竟刷题的目的是梳理解法思路而不是表演代码压缩术。4.2 忽略空间复杂度的后患LeetCode击败率的统计包含时间和空间两个维度很多人只盯着运行时间忽略了内存占用。比如哈希表存了过多冗余信息或者动规数组没有做滚动优化都会让内存排名偏低进而拉低综合击败率。更严重的是在真实面试中空间复杂度往往是考察点之一。我认识一位朋友解一道树的遍历题时直接开了全局数组保存所有节点虽然代码能跑过但空间复杂度O(n)明显不是最优。面试官接着追问能不能改成O(1)空间他一时语塞。所以刷题时每次都要问自己空间能不能再压这才是高击败率的正道。4.3 只看击败率不分析真实复杂度击败率是个数字但它受提交时间、评测机负载和同语言提交数量的影响波动很大。我见过有人用同一个代码反复提交只为刷出一个击败100%的截图这其实是在浪费时间。击败率可以当作参考但真正决定代码水平的还是时间复杂度和空间复杂度。从记录笔记的角度来说与其纠结“这次是不是100%”不如记录“这个解法的时间复杂度是O(n log n)空间是O(1)”。这样哪怕下次提交击败率只有90%你也清楚解法本身的层次并没有变差。数据波动是常态复杂度优劣是本质。5. 建立可持续的刷题节奏计划、复盘与心理建设5.1 制定按主题而非按难度的刷题计划很多人的刷题计划是“从Easy到Hard线性推进”结果往往是Easy题刷得想吐Hard题永远不敢碰半个月后热情耗尽。我试过按主题来刷一周集中刷二分查找下一周集中刷动态规划再下一周集中刷图论效果显著好于按难度推进。按主题刷的好处是同一个套路在七八道题里反复出现你对它的理解会从“背模板”变成“内化”。比如二分查找刷完一组题之后看到“最小值最大化”“最大值最小化”这类表述条件反射就能想到二分。这种模式化认知正是高击败率解法能够稳定输出的前提。5.2 复盘笔记的正确打开方式写题解是我固定动作但复盘笔记和题解是两回事。题解是写给读者看的追求清晰完整复盘笔记是写给自己看的追求直击痛点。我的复盘笔记包含三块内容第一块是这题的卡点在哪比如“没想到用哈希表”“状态转移方程推错了”第二块是如果换一个数据范围解法要不要变比如n从100变成10^6暴力是否还能扛住第三块是能不能把解法推广到类似题目比如“这道题的解法稍微改改就能用于无重复字符的最长子串”。这个复盘习惯坚持了半年之后我的解题速度有了明显提升。原因是很多看似无关的题在复盘笔记的串联下都会互相印证思路的迁移自然了很多。还有一点很重要复盘笔记要定期重读不是写完就丢。一个月前留下的卡点一个月后可能已经成了常识这种进步感对维持动力非常关键。5.3 保持心态稳定的方法我见过不少朋友刷题时情绪起伏特别大一道题AC了觉得自己是天才一道题卡了一下午就觉得自己不适合编程。这种心态对长期的刷题计划危害很大。我的建议是把“不会做”当成正常状态把“通过思考或查阅题解学会”当作真正的收获。这里分享一个实际有用的策略每道题给自己设定一个“思考时值”比如30分钟时间到了还写不出来就去看题解。看题解之后不是复制粘贴而是关掉页面重新自己写一遍并记录下“为什么我没想到”和“这个思路的触发条件是什么”。这样就算这次没有独立AC能力值依然在涨。遇到特别难啃的题隔几周再重做一遍往往会有豁然开朗的感觉。另外我每周都会固定打一次LeetCode周赛周赛的限时压力能逼你在更短时间内完成从建模到优化的全过程对提升实战状态很有帮助。但周赛成绩起伏也很大别把单次排名看得太重重要的是通过周赛发现自己在哪些类型题上容易卡壳然后在下周的专题计划里补强。5.4 记录“击败100%”的正确姿势最后说说记录这件事。我选择在题解里把“击败100%”作为标题的一部分不是因为它能证明我有多厉害而是因为它是一个很好的记忆锚点。看到这个标题我就能想起当初为了优化那一点点时间做了哪些尝试也能让读者一眼知道这个解法在性能上是有参考价值的。但记录时我会在正文里写清楚场景比如“这是2024年3月的提交数据Python 3版本击败100%但时间复杂度是O(n)”。这样哪怕日后击败率波动这段记录依然有研究价值。毕竟真正值得记录的从来都不是那个数字本身而是获得那个数字背后完整、可复现的思考路径。如果你刚开始刷题不必急着把击败率当作KPI。先从一个专题入手建立复盘的节奏你会发现当你能稳定输出清晰优雅的解法时击败100%只是水到渠成的副产品。