企业官网建设流程全解析

第二天打卡，题号 85-90。说实话，这一组题比想象中烧脑，最大矩形和扰乱字符串都属于那种“一看就会，一写就废”的类型。不过把六道题刷完再回头看看，知识点其实很集中：单调栈、链表切割、递归记忆化、双指针、位运算、回溯去重。这篇就是我的完整复盘，已经把这几天踩过的坑、绕过的弯、以及面试时容易被追问的细节都整理出来，给同样在刷题的朋友做个参考。

先说清楚这篇内容适合谁：如果你正在准备算法面试，或者刚开始按题号顺序刷 LeetCode，想看看 85-90 题怎么快速摸清套路，可以参考我的思路。我尽量把代码和推理过程都写出来，不搞“只贴答案不解释”那一套。

1. Day 2 整体复盘：这六道题到底在考什么

1.1 为什么按题号顺序刷？我的节奏安排

很多朋友纠结刷题顺序，到底是按标签分类刷，还是按题号顺序刷？我个人的习惯是按题号顺序，每天固定量。原因很简单：按标签刷容易陷入舒适区，今天全是双指针，明天全是二叉树，练多了会产生“我会了”的错觉，换到综合场景就抓瞎。按题号顺序刷，每天跟开盲盒一样，动态规划、链表、递归、位运算轮着来，强迫你把每个模块的知识捡起来。

Day 1 刷完前面的题之后，Day 2 正好轮到 85-90。我的节奏是上午先不翻题解，自己硬想 20 分钟，没思路就标记一下，然后看题解理解核心解法，晚上再不看代码手写一遍。这么做的好处是白天想过的思路即使错了，也能在脑子里留下痕迹，晚上重写时记忆特别牢。

1.2 六道题的知识点分布与难度评估

先把这六道题的整体情况摆出来，方便大家一眼看清今天要面对的是什么：

从难度分布就能看出来，这六道题是“两难两中一简一易”的混合组合，压力主要压在 85 和 87 上。但这两题恰恰是今天收获最大的地方，因为它们不是单纯考你背模板，而是考你怎么把一个陌生问题拆成已经做过的问题。

2. 从暴力到优化：逐题拆解 85-90

2.1 第85题 最大矩形：单调栈才是分水岭

题面很简单：给定一个由 0 和 1 组成的二维矩阵，找出只包含 1 的最大矩形面积。第一次看到这道题，最自然想到的是暴力枚举所有矩形，四个边界一确定，再检查内部是否全 1，复杂度直接爆炸，O(m^3 * n^3) 级别的，写完面试官肯定摇头。

正确的打开方式是把它转换成“柱状图中的最大矩形”，也就是之前刷过的第 84 题。具体做法是：按行遍历，把每一行看成直方图的底边，heights[j]表示当前位置往上连续为 1 的高度。遍历到当前行时，如果matrix[i][j] == '1'，高度加一，否则清零。然后对heights调用 84 题的单调栈方法，算出以当前行为底的最大矩形面积，逐行更新答案。

def maximalRectangle(self, matrix: List[List[str]]) -> int: if not matrix or not matrix[0]: return 0 rows, cols = len(matrix), len(matrix[0]) heights = [0] * cols ans = 0 for row in matrix: for j in range(cols): if row[j] == '1': heights[j] += 1 else: heights[j] = 0 ans = max(ans, self.largestRectangleArea(heights)) return ans def largestRectangleArea(self, heights: List[int]) -> int: stack = [-1] max_area = 0 heights.append(0) for i, h in enumerate(heights): while heights[stack[-1]] > h: idx = stack.pop() height = heights[idx] width = i - stack[-1] - 1 max_area = max(max_area, height * width) stack.append(i) return max_area

单调栈的核心逻辑是：遍历到当前柱子时，把栈里所有比它高的柱子都弹出来计算面积，因为对那一根柱子来说，当前这个更矮的柱子就是它的右边界；而它左边第一个比它矮的柱子就是左边界，左边界还在栈里。利用栈维护的单调递增性质，能在 O(n) 时间内求出每根柱子能扩展的最大宽度。

这个过程我调试时踩了一个坑：heights.append(0)不能漏。如果不加这个哨兵柱，遍历结束后栈里剩下的柱子没人帮它们触发“出栈计算面积”，会直接漏算。我第一次写就是漏了这行，样例怎么跑都少答案，排查了半天才发现是边界处理问题。这个教训不只是在 85 题有用，凡是单调栈题都要记得在数组末尾补一个最小值来清空栈。

这题的时间复杂度是 O(m * n)，因为每行更新高度是 O(n)，调用一次单调栈 O(n)，m 行就是 O(m * n)，空间 O(n)。

2.2 第86题 分隔链表：哑节点的妙用

题目要求把链表中小于 x 的节点排在大于等于 x 的节点之前，而且要保持节点之间的相对顺序不变。比如1->4->3->2->5->2，x = 3，结果应该是1->2->2->4->3->5。

难点在于“相对顺序不变”，这意味着不能排序，也不能随意交换节点。最干净的做法是创建两个哑节点，一个用来串所有小于 x 的节点，另一个用来串所有大于等于 x 的节点，遍历一次原链表，按值决定挂到哪条链上，最后把两条链拼起来。

def partition(self, head: ListNode, x: int) -> ListNode: small_dummy = ListNode(0) large_dummy = ListNode(0) small, large = small_dummy, large_dummy cur = head while cur: nxt = cur.next if cur.val < x: small.next = cur small = small.next else: large.next = cur large = large.next cur.next = None cur = nxt small.next = large_dummy.next return small_dummy.next

这里有个特别容易忽略的细节：cur.next = None必须加。如果不把当前节点从原链表里摘出来，最后拼接的时候，两条链之间可能会出现环。因为节点在挂到 small 链后，它的 next 还指向原来链表的下一个节点，等 large 链也串起来，万一二者指向同一个节点，循环链表就出来了。我调试的时候真遇到过这个问题，表现为程序直接死循环或者“Time Limit Exceeded”。

另外就是large_dummy.next要提前保存，因为large_dummy.next在拼接后会被写入 small 链的尾部，但如果在拼接时访问large_dummy.next没有问题；真正需要注意的是最后返回的是small_dummy.next，不是small本身。因为 small 指针已经移动到链尾了，small_dummy.next才是头节点。

时间复杂度 O(n)，空间 O(1)，这里说的 O(1) 是不算新节点占用的空间，哑节点只是固定两个，非常漂亮。面试时这道题还有一个常见追问：能不能用原地拆分？答案就是上面这个做法，因为我们是把原链表的节点拆下来再挂到新链上，本身就是原地操作，只是额外用了两个哑节点。

2.3 第87题 扰乱字符串：递归里藏着记忆化

这题应该是今天最抽象的一道。题目本身描述很绕：给定两个字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。所谓扰乱，就是把字符串从任意位置分成两个非空子串，然后可以选择交换这两个子串的位置，再对子串递归地做同样的操作。

换句话说，一个字符串在“翻转”若干次之后，能变成另一个字符串。第一次读题我脑子里全是浆糊，后来画了个树才明白：每次划分把字符串分成左右两半，递归判断左右两半是否匹配，关键是有两种匹配方式——不交换，左对左、右对右；或者交换，左对右、右对左。

from functools import lru_cache class Solution: def isScramble(self, s1: str, s2: str) -> bool: @lru_cache(None) def dfs(a: str, b: str) -> bool: if a == b: return True n = len(a) # 剪枝1：字符构成不一致，直接返回 False if sorted(a) != sorted(b): return False # 枚举所有可划分的位置 for i in range(1, n): # 不交换 if dfs(a[:i], b[:i]) and dfs(a[i:], b[i:]): return True # 交换 if dfs(a[:i], b[n-i:]) and dfs(a[i:], b[:n-i]): return True return False return dfs(s1, s2)

关键点在于两个剪枝。第一个剪枝是a == b直接返回 True，因为同一段子串不需要再递归。第二个剪枝是字符计数必须相同，如果两个子串的字符组成都不一样，那无论怎么翻转都不可能相等，直接返回 False。这两个剪枝能把原本指数级的递归空间大幅压缩，再配合lru_cache做记忆化，实际跑起来很快。

这道题还有一个很有意思的视角：它可以看成一个区间 DP 问题，状态是(a 的起始位置, b 的起始位置, 长度)，转移就是枚举划分点。从递归到区间 DP，其实就是把递归过程中的状态显式记录下来，面试时如果被追问“能不能改成动态规划”，你可以沿着这个思路回答。但第一次做，递归 + 记忆化是最好理解的，先写对再谈优化。

复杂度上，记忆化之后每个状态只会被计算一次，状态数是 O(n^3)，枚举划分点又是 O(n)，所以总复杂度 O(n^4)，n 是字符串长度。看着吓人，但实际因为剪枝很凶，LeetCode 上的用例都能过。

2.4 第88题 合并两个有序数组：从后往前是精髓

这题标签是“简单”，但我觉得它是今天最容易翻车的题之一。题面：两个有序数组 nums1 和 nums2，把 nums2 合并到 nums1 中，不返回新数组，直接原地改。nums1 的长度是 m + n，前 m 个是实际元素，后面 n 个补零，正好用来放 nums2 的元素。

如果按正向思维从头开始合并，问题就来了：把 nums2 的小元素插到 nums1 前面时，会把 nums1 原有的元素往后挤，需要移动大量数据。更严重的是，可能覆盖还没处理的元素。所以标准解法是从后往前填：比较两个数组的末尾元素，谁大就放到 nums1 末尾，这个位置一定已经空出来了，不会覆盖任何有效元素。

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: i, j, k = m - 1, n - 1, m + n - 1 while j >= 0: if i >= 0 and nums1[i] > nums2[j]: nums1[k] = nums1[i] i -= 1 else: nums1[k] = nums2[j] j -= 1 k -= 1

这个代码的精妙之处在于：循环条件是while j >= 0，意味着只要 nums2 还没处理完就继续；如果 nums1 先处理完，i 变成 -1，那剩下的 nums2 元素直接按原顺序铺到 nums1 前面；如果 nums2 先处理完，循环结束，nums1 剩余元素已经在正确位置，不用动。这就是为什么不需要额外处理“nums1 有剩余”的情况。

我写这题时犯过一个低级错误：把while j >= 0写成while i >= 0 and j >= 0，结果 nums1 先遍历完时，nums2 还剩一堆元素没合并进去，输出完全错乱。记住，这题的主导者是 nums2，只要 nums2 没清空，就必须继续填。

时间复杂度 O(m + n)，空间 O(1)，这也是归并排序 merge 阶段的经典写法，算是面试里最基础的一题，但以后写归并排序会觉得格外顺手。

2.5 第89题 格雷编码：位运算的对称性之美

格雷编码是指 n 位二进制数字的序列，要求相邻两个数字的二进制表示恰好有 1 位不同，包括首尾两个数字，也只差 1 位。这道题要求输出以 0 开头的任意一个有效格雷编码序列。

刚看到这个题，最容易想到暴力回溯，每一位试着变，复杂度 2^n 乘以检查开销，写着写着就发现回溯很难控制“首尾相接”这个条件。标准解法其实非常优雅：格雷编码的第 i 个数字 = i ^ (i >> 1)。一行公式搞定。

def grayCode(self, n: int) -> List[int]: res = [] for i in range(1 << n): res.append(i ^ (i >> 1)) return res

以 n = 2 为例：i 从 0 到 3，算出0 ^ 0 = 0、1 ^ 0 = 1、2 ^ 1 = 3、3 ^ 1 = 2，序列是[0, 1, 3, 2]，检查一下：0（00）和 1（01）差 1 位，1（01）和 3（11）差 1 位，3（11）和 2（10）差 1 位，2（10）和 0（00）差 1 位。

为什么这个公式成立？可以这样理解：i 从 0 增加到 i+1 时，二进制最低连续几位会翻转，比如从 0111（7）变到 1000（8），最低三位从 1 变 0，最高位从 0 变 1。i ^ (i >> 1)恰好能把“变化的位置”编码为新的比特差异，所以相邻 i 得到的格雷码彼此只差 1 位。不需要死记公式，理解了这层就能迁移到别的编码问题。

这题面试时可能追问另一种做法：镜像生成。已知 n-1 位的格雷码序列，把它倒序，再在最高位补 1，就能得到 n 位格雷码。两种做法等价，公式法代码更短，但镜像生成更直观。我建议两个都掌握，面试官让解释原理的时候，用镜像生成讲起来更形象。

2.6 第90题 子集 II：回溯去重的关键在排序

子集 II 是 78 题“子集”的升级版，区别在于数组里可能有重复元素，要求返回所有不重复的子集。比如nums = [1, 2, 2]，如果按 78 题的无脑回溯，会得到两个[2]、两个[1,2]，必须去重。

去重有两种思路。第一种是拿 set 去重，简单粗暴，但这不是面试官想听的，而且空间复杂度高。第二种是回溯时跳过同一层的重复元素，这是标准解法。前提是先排序，让相同的元素紧挨在一起。

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() res = [] def backtrack(start: int, path: List[int]) -> None: res.append(path[:]) for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return res

这里的判断条件是i > start，不是i > 0，这个细节非常关键。i > start的含义是：在“同一层”的枚举中，跳过后面出现的重复元素；但如果这个重复元素是作为下一层递归的第一个元素出现的，它就可以用。举个例子，[1, 2, 2]，第一层枚举到第二个 2 时，因为i == 2 > start == 0且nums[2] == nums[1]，所以跳过，这就避免了重复的子集[2]；可是在递归进去之后，start变成 1，第二个 2 作为路径中的第二个元素是完全合法的，比如[1, 2, 2]这个子集就依赖它。如果错误地写成i > 0，所有重复元素都会被砍掉，连[1, 2, 2]本身都出不来，那我就又踩坑了。

回溯题的复杂度很难精确表示，对于 n 个元素的数组，子集个数最多是 2^n，每次生成一个子集要复制 path，所以最坏 O(2^n * n)，空间上递归深度 O(n)。

3. 刷题过程中的调试与环境经验

3.1 我在哪里刷题：本地环境与在线判题的选择

写这几道题时，我的习惯是先在本地的 VS Code 里跑，再粘到在线判题环境提交。本地调试最大优势是能看到完整堆栈和print输出。像 85 题这种数组题，我一般会在largestRectangleArea里临时打印每根柱子的左右边界；86 题链表题，我会写一个小函数把链表打印成数组，一眼看出有没有成环。

不要小看这些土办法。单调栈的边界、链表的指向、递归的调用顺序，这些在脑子里跑一遍容易漏，实际打印出来才直观。等本地跑通了，再贴到在线判题确认，能省不少罚时。

不过也要提醒一句：本地调试归调试，最后提交前一定把多余的print删掉，不然刷题记录里全是输出错误。我见过太多人交了带 print 的代码，然后被网络判题误判超时。

3.2 几个让我走了弯路的地方

今天最大的弯路在 85 题，我把heights数组放在largestRectangleArea里又重新初始化了一遍，结果每行算出来的都是同一个东西，debug 了半天才发现问题出在“行与行之间高度是累积的，不是重置的”。“累计”这个特性是这道题能复用 84 题的核心，没有它每行都是一个独立的直方图，根本无法体现“从本行往上连续 1 的数量”。

另一个弯路在 87 题。我第一次直接用sorted(a) != sorted(b)做剪枝，但忘了在dfs里先判断a == b。结果递归到长度为 1 时，sorted("a") == sorted("a")成立，但循环范围range(1, 1)为空，函数返回 False，导致两个完全相同的字符串都判不了 True。后来补上a == b的早返回，才跑通。这里能看出来，递归题的“最小子问题出口”往往就是能不能跑通的命门。

4. 常见问题与排查技巧速查

4.1 这组题最常踩的坑

我整理了一张速查表，把今天遇到的问题和排查思路都列出来，以后复习直接看这张表。

这些坑单独看都不严重，但在面试高压环境下很容易犯。我的建议是每道题刷完后，把踩过的坑浓缩成一句话写在题解旁边，方便隔几天回看。

4.2 面试官追问时怎么扩展

刷题不只是为了 AC，更要在面试时体现深度。以这组题为例，常见追问包括：

85 题一定会被问到“你用的单调栈是干嘛的”，给你一个最简单的一维数组，让你现场把每根柱子的左右边界求出来。只要你把“右边界是第一个更矮的柱子，左边界是栈里剩下的前一个元素”讲清楚，这题就算过关。

86 题追问经常是“如果要求保持稳定性怎么办”。因为单链表的拆分天然是稳定的，按原链表顺序挂到两条链上，不会打乱相对顺序，所以直接说“我这个解法本身就是稳定的”。

87 题追问多半是“复杂度能不能优化”。可以从递归记忆化讲到区间 DP，转移方程用状态(i1, i2, len)表示“从 s1 的 i1 开始和 s2 的 i2 开始、长度为 len 的子串是否能扰乱匹配”，把递归改成三重循环，虽然思维量大，但状态转移清晰。

88 题追问是“为什么从后往前不会覆盖”。因为后往前填的位置是 m + n - 1 到某个位置，这些位置在合并前都未使用或已经处理过，不可能覆盖 nums1 还没参与比较的元素。

89 题追问通常是“解释一下i ^ (i >> 1)为什么正确”。建议用镜像生成的例子先讲清楚格雷码的构建规则，再说明这个公式在计算上等价于镜像生成。

90 题追问是“去重的本质是什么”。本质是保证重复元素在每一层只会被选中一次，而不是在路径的不同位置反复使用。

5. 复习策略与下一步计划

5.1 当晚怎么消化这六道题

刷完不等于会了，我晚上会做三件事。第一，不看代码，把每道题的核心思路写成一页纸，类似“85 = 逐行算高度 + 84单调栈”“90 = 排序 + 同层去重”，用一两句话逼自己抓住本质。第二，把当天写过的代码先全部藏起来，给自己 15 分钟，在白纸上重新实现一遍，尤其是 85 和 87。第三，用费曼的方式讲给自己听，比如“让我解释一下为什么格雷编码公式相邻只差一位”，讲不下去的地方就是下次复习的重点。

这几件事看起来麻烦，但效果比再刷十道新题还明显。因为刷题真正要练的是从“看懂题解”到“独立写出”之间的那段距离，这个距离只能靠主动回忆来缩短。

5.2 后续安排

按我的计划，接下来一天会刷 91-96，覆盖解码方法、反转链表 II、二叉树中序遍历、不同的二叉搜索树 II、恢复二叉搜索树、不同的二叉搜索树。这个区间同样硬核，既有动态规划又有树的 Morris 遍历。

我会把今天踩过的坑，比如heights.append(0)、cur.next = None、i > start这些细节写进错题本，后面每周复习一次。建议你也准备一个类似的错题本，不需要很复杂，记一条坑、一行原因、一个解法就够了，比收藏一堆题解有用得多。

刷题这件事，短期拼的是题量，长期拼的是复盘质量。Day 2 这六道题能坚持下来，强度不算低，但收获确实实在在。继续保持这个节奏，几天后回头再看，你会发现自己看题的视角已经不一样了。