今天按计划刷到LeetCode第85-90题正好是day2。这一批题目说不上简单但确实刷得过瘾——最大矩形、分隔链表、扰乱字符串、合并有序数组、格雷编码、带重复元素的子集六道题把数组、链表、字符串、位运算、回溯、动态规划轮了一遍几乎像是在刻意给我做题型交叉训练。如果你刷题处在中期想通过一组题把多个常用模板一次过一遍这六道是很合适的组合。刷完我最大的感受是题号靠得近不代表思路靠得近。看起来只有六道题实际涉及的思维模型超过十种。我打算把这天的复盘完整写下来重点不是贴代码而是指清楚每道题的破题点、容易写崩的地方以及为什么这道题放在第二天刷特别有效。1. 我为什么安排85到90当第二天的任务题目定位与考点分布先把这六道题摊开来看。85题最大矩形困难核心是二维矩阵转柱状图86题分隔链表中等链表双指针加哑节点87题扰乱字符串困难递归加记忆化88题合并两个有序数组简单但原地归并有边界细节89题格雷编码中等位运算或者镜像法90题子集II中等回溯加排序去重。从难度分布来说这一组并不是均匀的85和87明显比其余几道硬但正是这种“中间塞两颗硬钉子”的节奏能逼自己跳出舒适区。我选择在第二天刷它们的另一个原因是它们彼此之间没有强依赖但又能共享一些底层模板。比如85题的单调栈如果之前刷过84题会轻松很多90题的排序去重模板之后做子集、组合、排列时会反复出现88题从后往前归并的思路和86题链表双指针本质上是同一个“倒着处理顺序”的思路。我的建议是如果你刚开始刷题不到一周别急着把这一组全部做完。先把84题拿出来单独刷一下再回来碰85题否则现场推导单调栈容易卡住。如果已经有二三十道题的基础那这一组完全可以按Day2计划来做。1.1 六道题的难度与核心考点速览题号题名难度核心考点推荐用时85最大矩形困难行列累加 单调栈40分钟86分隔链表中等链表哑节点 双指针20分钟87扰乱字符串困难递归 记忆化搜索35分钟88合并两个有序数组简单双指针逆向归并15分钟89格雷编码中等镜像法 / 位运算25分钟90子集II中等回溯 排序去重25分钟这张表是我实际执行时的参考。把85放在第一位是有用意的状态最好的时候先啃硬骨头后面就算卡一下也不会心慌。87题虽然也难但它和85题的解法体系不同前面已经完成了“最大矩形”心态上会更稳。1.2 这一组题目覆盖的通用能力这六道题如果只看考点你会发现它们几乎没重叠。但刷完之后我更愿意把它理解成三种能力的组合把高维问题降维。85题把二维矩阵变成一维柱状图这种“压缩”思维在后续遇到岛屿、区域、直方图类题目时很有用。在顺序敏感的场景里控制指针。86题和88题一个链表一个数组本质上都是“不能破坏相对顺序地重新排列元素”只要掌握了从后往前或者用哑节点保护头部的思路就能迁移。在递归搜索中做剪枝和去重。87题做字符频率剪枝90题做同层重复剪枝核心都是“减少无效分支”。把这三种能力拆出来对我自己后续刷题有很大帮助。因为很多题看起来是新题剥掉外壳后仍然是这三种模型之一。2. 最大矩形85是这六题里最硬的一块二维矩阵怎么降维成柱状图85题的题目描述很短给一个仅包含0和1的二维矩阵找出只包含1的最大矩形面积。我第一次看到时脑子里直接冒出“二维动态规划”这个选项但真去设计状态转移会发现非常绕而且很容易漏掉长宽都比较大的矩形。后来我把解法拆成两步才算真正理解。第一步把二维矩阵逐行压缩成一个高度数组heights。heights的长度等于矩阵列数遍历到第i行时heights[j]表示从第i行往上连续为1的层数。遇到0就清零。这就等于把每一行都看作柱状图的底面对每一行调用一次“直方图最大矩形面积”的算法。第二步用单调栈求柱状图最大矩形。2.1 为什么暴力枚举会超时以及逐行压缩的原理暴力枚举是枚举矩形左上角和右下角再检查内部是否全是1复杂度至少是O(m^2 n^2)稍微大一点的矩阵就撑不住。逐行压缩的好处是把二维问题拆成了多个一维子问题。你可以想象每一列都在“堆萝卜”碰到0就把这一列的萝卜拔掉只统计连续未断的1。这样每一层的heights都准确表达了当前行的“连续向上高度”。举个例子矩阵1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0第一行的heights是[1,0,1,0,0]第二行是[2,0,2,1,1]第三行是[3,1,3,2,2]第四行是[4,0,0,3,0]。每次计算完一行就对当前heights求一次最大矩形面积最后取全局最大。这个思路里最需要提醒自己的是heights是上一行累积下来的一旦当前行出现0对应列必须归零否则会把上一行的高度带到本行计算出不存在的矩形。2.2 单调栈的现场推导宽度计算别犯傻单调栈的思路可以这样理解对于每一个柱形找到左边第一个比它矮的位置left和右边第一个比它矮的位置right那么以当前柱高能形成的最大矩形宽度就是right - left - 1。为了高效找到这个边界我们维护一个递增栈。遍历过程中如果当前高度小于栈顶高度说明栈顶的右边矮柱已经出现可以弹出栈顶并结算面积。栈里存的是下标不是高度这是新手的常见误区。我一开始写的时候宽度算错过。比如当前遍历到下标i弹出下标cur此时新的栈顶下标为left那么宽度应该是i - left - 1而不是i - cur。原因是cur右边第一个矮柱就是i左边第一个矮柱是left所以矩形范围其实是(left, i)开区间内的柱子宽度只包含中间的柱子不包括左右两个边界。为了省事我通常会在heights末尾push一个0让最后一次弹出的柱子也能结算这样不用额外判断栈是否为空。def largest_rectangle_area(heights): h heights [0] stack [] res 0 for i, cur in enumerate(h): while stack and h[stack[-1]] cur: idx stack.pop() left stack[-1] if stack else -1 res max(res, h[idx] * (i - left - 1)) stack.append(i) return res这个模板可以背下来但最好还是自己手动推导一遍尤其要理解h.append(0)为什么能让循环结束时不需要额外清理栈。如果你直接原地append记得调用后把末尾的0再切掉避免影响外层循环。外层代码就简单了def maximal_rectangle(matrix): if not matrix or not matrix[0]: return 0 heights [0] * len(matrix[0]) max_area 0 for row in matrix: for c in range(len(row)): if row[c] 1: heights[c] 1 else: heights[c] 0 max_area max(max_area, largest_rectangle_area(heights)) return max_area我实际调试时发现这个解法虽然时间复杂度是O(m*n)但系数不小因为每一行都要调用一次单调栈。缺点是没法提前剪枝但胜在思路清晰面试时是标准答案。如果你对单调栈还不够熟建议找84题先用同样的函数跑一遍再回来做85题。3. 分隔链表和扰乱字符串一道靠哑节点一道靠递归边界86题和87题一道链表、一道字符串看起来八竿子打不着但它们在“边界的处理”上有同一个特点代码不复杂可一旦边界没控制好就会出莫名其妙的结果。我分别说一说实际踩到的坑。3.1 86分隔链表两个哑节点顺序别接反题目要求把链表中小于x的节点移到前面大于等于x的节点保持在后面并且保持原有的相对顺序。最稳妥的解法不是原地改指针而是准备两条新链表一条存小于x的节点一条存剩余节点最后串起来。这个过程中两个哑节点能非常自然地保护链表的头部不让你去处理“当前头部要不要单独判断”。我一开始觉得原地改更帅写的时候发现两个问题第一如果原链表头节点就小于x你需要改head第二把节点接到新链表尾部时如果没有保存next原链表后续节点会丢。所以我最终写成了这样def partition(head, x): small_dummy ListNode() large_dummy ListNode() ps, pl small_dummy, large_dummy cur head while cur: nxt cur.next if cur.val x: ps.next cur ps ps.next else: pl.next cur pl pl.next cur nxt pl.next None ps.next large_dummy.next return small_dummy.next关键在于遍历时先保存nxt cur.next否则把cur接到新链表后cur的next信息还在旧的后面后续遍历会乱。另一个关键点是最后一定要把large链表尾部的next置空否则可能出现环。很多演示代码省略了pl.next None实际跑起来只有在你运气好时才能得到正确答案运气差就直接死循环。这类链表分区题我个人的经验是“永远用哑节点起步”。哪怕是LeetCode常见的反转链表II、删除倒数第N个节点哑节点都能省掉大量条件分支。3.2 87扰乱字符串递归不剪枝等于是指数爆炸扰乱字符串的定义建议先理解成“选择一个位置切一刀得到两个子串。然后你可以决定是否交换这两个子串再对每个子串继续做同样的操作”。给定两个字符串s1和s2问能不能通过这种方式得到另一个。最朴素的递归是枚举所有切分点每个切分点产生两种匹配情况不交换s1[:i]对应s2[:i]s1[i:]对应s2[i:]交换s1[:i]对应s2[-i:]s1[i:]对应s2[:-i]任意一种成立就返回True。如果直接这么写n稍微大一点就会超时因为同样的子串组合会被重复计算。解决办法很简单加一个记忆化装饰器把(s1, s2)作为缓存键。真正容易忽略的是剪枝。如果不检查两个字符串的字符构成是否相同递归会进入大量注定失败的节点。比较频率或者直接排序再比较都能显著减少计算量。我用排序代码最省事from functools import lru_cache lru_cache(None) def is_scramble(s1, s2): if s1 s2: return True if len(s1) ! len(s2): return False if sorted(s1) ! sorted(s2): return False n len(s1) for i in range(1, n): if is_scramble(s1[:i], s2[:i]) and is_scramble(s1[i:], s2[i:]): return True if is_scramble(s1[:i], s2[-i:]) and is_scramble(s1[i:], s2[:-i]): return True return False这个递归虽然有记忆化但要小心lru_cache的键是字符串切片后生成的新字符串数量还是可观的。实际提交时Python能过但如果你不使用排序剪枝在大数据量的用例上可能还是会超时。面试时如果接着被问“时间复杂度是多少”不要只说O(n^4)因为加了剪枝后实际会好很多但理论上最坏情况仍然是O(n^4)级别。87题另外一个值得琢磨的地方是它和区间DP有联系。把递归式转成dp[i][j][k][l]会变成四维很难写。我的建议是记忆化递归优先毕竟代码短、不容易出错。4. 合并有序数组、生成子集和格雷编码三个“看起来简单”的题一个数组题一个回溯题一个位运算题难度标签都不算高但陷阱都有点隐蔽。这组题最考验的不是思路而是细节。4.1 88合并两个有序数组原地归并从后往前是铁律这题题目很直白nums1长度是mn前m个位置存有效元素nums2长度是n。让你把nums2合并到nums1里要求不断新开数组。如果从前往后归并nums1的有效元素会被覆盖掉所以必须从后往前。三个指针p1指向nums1有效尾p2指向nums2尾p指向nums1尾部。def merge(nums1, m, nums2, n): p1, p2, p m - 1, n - 1, m n - 1 while p2 0: if p1 0 and nums1[p1] nums2[p2]: nums1[p] nums1[p1] p1 - 1 else: nums1[p] nums2[p2] p2 - 1 p - 1 return nums1这里的循环条件只有p2 0因为当p1先小于0时nums2剩下的元素仍然需要继续复制到nums1前面而如果p2先小于0则说明nums2已经全部归并完毕剩下的nums1本来就是有序的不需要再移动。我刚学的时候总是写成while p1 0 or p2 0结果在p1 0时越界访问nums1[p1]这是典型的边界失误。从这个题提炼出来的经验在后续很多双指针题目里都适用需要原地覆盖时优先考虑从后往前填。4.2 90子集II排序去重靠的是i start不是i 0子集问题最经典的模板是回溯dfs(start)每次递归进入时先把当前path拷贝到结果里。但如果数组里有重复元素比如[1,2,2]直接回溯会产生两个相同的[1,2]。解决办法是先排序然后在同一层内跳过和前一个元素相同的元素。很多初学者以为只要写“if i 0 and nums[i] nums[i-1]: continue”就行这样会漏解。举一个具体例子输入[1,2,2]。在递归到start0时我们遍历i0、1、2。当i1时被跳过那我们就永远不会选择第二个2作为这一层的起点但递归到i2时因为前一个元素nums[1]2与nums[2]2相同也会被跳过实际上如果错误地使用i 0在start0这一层i1和i2都会被跳过连[2]和[2,2]都会丢掉。正确的写法是跳过条件的比较对象是当前层的起始位置startdef subsets_with_dup(nums): nums.sort() res [] path [] def dfs(start): res.append(path[:]) for i in range(start, len(nums)): if i start and nums[i] nums[i - 1]: continue path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res为什么i start因为当i等于start时无论和前一个元素是否相同它都是当前层的第一个可选元素必须允许选。只有当i不是起始位置而且和前一个数相等时说明这个数在上一个分支里已经作为同样的选择出现过了再选就会在结果中产生重复子树。这个去重条件几乎可以无缝对接到组合总和II、全排列II等题目里值得专门记一笔。4.3 89格雷编码镜像法十几行就能写完别用回溯硬生成格雷编码的特点是每两个相邻数的二进制表示只差一位。最经典的构造方法是镜像法。拿n1来说序列是[0,1]。要生成n2先把n1的序列复制一份然后在前一半前面加0在后一半倒序前面加1得到[00,01,11,10]。这样相邻两个编码前半段的边界和后半段的边界分别只差一位中间由于原序列首尾相接也满足条件。代码上不需要真的去操作字符串只需要记录整数。每轮用1 i作为高位前缀把上一轮结果的反向副本再加上前缀追加到结果末尾def gray_code(n): res [0] for i in range(n): prefix 1 i res [x | prefix for x in reversed(res)] return res如果你对位运算熟悉还可以直接用公式生成所有编码第i个格雷码是i ^ (i 1)。比如n3时0到7分别右移一位再异或得到的序列就是[0,1,3,2,6,7,5,4]符合要求。我更喜欢镜像法因为它在面试时更容易被解释清楚而且公式法如果推倒台阶一紧张容易忘记。不过两种方法都值得写一遍因为格雷编码和二进制数之间的关系本身就是一道很有意思的位运算题。4.4 这三道题和85、87之间有什么隐藏联系88题的从后往前双指针和86题链表分隔里的“先保存旧连接、再重组”本质上都在避免覆盖或丢失信息。90题的排序去重和87题的频率剪枝一样都是在递归搜索里砍掉多余分支。89题的镜像法和85题的逐行累加则都是利用“已经解决好的子问题来构建新答案”。这些隐藏联系才是刷一组题最大的收获。5. 刷完这六道题后的复盘清单卡壳点、模板与个人体会最后做一次完整复盘把我在这一天的实际操作经验沉淀下来。如果你也打算按这个顺序刷下面的内容应该能帮你少走弯路。5.1 六道题最容易出错的地方题号最易出错点我的应对85宽度计算用了i - cur导致面积算大或算小记住宽度 右边界 - 左边界 - 1栈里存下标86忘记保存cur.next链表成环每次遍历先nxt cur.next结束时置空大链表尾87不剪枝递归直接超时先排序判断字符频率是否一致再加记忆化88循环条件写成p1 0 or p2 0越界只用while p2 0让nums1剩余元素自然留在前面89想用回溯暴力生成编码n12就卡死用镜像法本质是倒序复制再加前缀90去重条件写成i 0漏掉[2,2]这类结果改成i start只跳过同一层内重复元素这六个坑我几乎全部踩过一遍有些还是看别人报错才发现。所以如果你写的时候恰好也犯了一样的错不用太沮丧这就是这一组题本身的坑位。5.2 值得专门背下来的三个小模板第一个是单调栈求最大矩形的模板85题和84题通用。第二个是回溯去重模板90题、组合总和II、全排列II通用。第三个是原地数组归并从后往前的模板88题和部分双指针题通用。把这些模板理解透比单纯记住六道题的答案重要得多。5.3 个人实操体会这六道题合在一起刷完大概花了我一个下午加晚上。85题单独卡了将近四十分钟原因不是不会单调栈而是没想清楚“二维矩阵压成一维高度”之后每次遍历完一行都需要调用一次84题的函数。一旦想通这道题的结构后面86、88、89、90都算顺滑。87题倒是费了些时间主要是递归分支的条件容易写反建议把所有切分情况在纸上画一遍再动代码。我自己在day2结束后最想强调的是不要因为某道题标着“中等”就掉以轻心也不要因为标着“困难”就发怵。85题实际上是把一道中等题84题套上一个矩阵外壳87题的递归思路如果理解透彻写在纸上的代码不超过二十行。刷完这一组我最大的体会是算法题里很多“难题”其实是在“基础模板”上叠加了一层转化。这个转化能力只能靠多练而85到90正好是练转化能力的一组高质量样本。