1. 从一串题号说起：这份刷题清单到底在练什么
LeetCode 2016 37,65,212,84,130,218——第一次看到这串数字，很多人会愣一下：2016是年份还是题号？后面那六个数字又是什么？其实这是刷题圈里很常见的一种记录方式，2016大概率是某个题单编号或者某次集中训练的批次标记，而37、65、212、84、130、218这六道题，才是真正的主角。它们分别是：解数独、有效数字、单词搜索II、柱状图中最大的矩形、被围绕的区域、天际线问题。六道题横跨回溯、字符串解析、字典树加回溯、单调栈、并查集/深度优先搜索、扫描线加堆这几个硬核方向，难度从Hard到Hard不等，没有一道是省油的灯。
如果你正在按LeetCode热门100题或者leetcode刷题指南推进，突然撞上这么一组题，大概率会有两种反应：要么觉得“这都什么怪物”，要么觉得“终于来点有意思的了”。我属于后者。这六道题有一个共同特点——它们都不是靠背模板能过的，每一道都在逼你理解数据结构的本质，而不是套公式。解数独考的是回溯的剪枝艺术，有效数字考的是状态机的边界控制，单词搜索II考的是字典树和回溯的配合，柱状图最大矩形考的是单调栈的单调性维护，被围绕的区域考的是从边界反推的逆向思维，天际线问题考的是扫描线加优先队列的协同。
这篇文章适合谁看？如果你已经刷完了LeetCode简单题和大部分中等题，正朝着leetcode热门100题里的Hard部分推进，或者你正在准备周赛想突破Hard题的瓶颈，那这六道题就是很好的试金石。我不会只给你代码，我会把每道题的思考路径、踩坑记录、优化过程都摊开讲，让你看完能自己复现，而不是复制粘贴完事。
2. 解数独与有效数字：回溯和状态机的两种极致
2.1 解数独：回溯不难，难的是剪枝
37题解数独，规则大家都懂：9x9的盘面，每行每列每个3x3宫格都要填1到9且不重复。暴力回溯当然能过，但如果你真的写过暴力版本，就会发现它慢得让人想砸键盘。问题出在“每次填一个格子都要重新扫描行列宫格”这个操作上，时间复杂度直接爆炸。
我一开始的写法就是最朴素的那种：遍历每个空格，尝试1到9，每次尝试都用三层循环检查合法性。跑一个中等难度的盘面要好几秒，LeetCode上直接超时。后来我换了个思路——用三个布尔数组分别记录每行、每列、每个宫格已经用过的数字。具体来说，row[i][d]表示第i行是否已经填了数字d，col[j][d]表示第j列，box[k][d]表示第k个宫格。这样每次尝试只需要O(1)的检查时间，整体速度快了不止一个数量级。
但真正让解数独从“能过”变成“优雅”的，是选择填空顺序的优化。与其按从左到右从上到下的顺序填，不如每次优先填“候选数字最少”的那个空格。这个策略叫MRV（Minimum Remaining Values），是约束满足问题里的经典启发式。实现起来也不复杂：每次递归前扫描一遍所有空格，统计每个空格的合法候选数，选最少的那个先填。实测下来，这个改动能让某些极端盘面的求解时间从几百毫秒降到几毫秒。
注意：用位运算代替布尔数组可以进一步压缩空间。比如用
row[i]的一个整数的低9位表示第i行数字1到9的使用情况，检查时用(row[i] >> d) & 1，设置和撤销用异或操作。这个技巧在面试里写出来很加分，但可读性会下降，建议先写清楚布尔数组版本，再考虑优化。
还有一个坑是宫格索引的计算。第i行第j列属于哪个宫格？公式是(i / 3) * 3 + j / 3。这个公式我见过太多人写错，写成i / 3 + j / 3或者(i / 3) * 3 + (j / 3) * 3，前者会把不同宫格混在一起，后者直接越界。记住：宫格编号是0到8，行方向每3行换一个宫格行，列方向每3列换一个宫格列。
2.2 有效数字：状态机是唯一正解
65题有效数字，看起来简单，写起来想哭。题目要求判断一个字符串是否表示有效数字，规则包括：可以有前导空格和尾随空格，可以有正负号，可以有小数点，可以有指数部分，指数部分也可以有正负号，但小数点不能出现在指数部分，指数部分必须是整数，小数点前后至少要有一边有数字……
我第一次写的时候用了一堆if-else，结果提交了七次才过，每次都是某个边界条件没考虑到。后来我学乖了，直接上状态机。状态机的思路是把字符串的解析过程拆成若干个状态，每个状态根据当前字符转移到下一个状态，最后看是否停在接受状态。
具体到这道题，我定义的状态包括：起始状态、符号状态、整数部分状态、小数点状态、小数部分状态、指数符号状态、指数整数状态、结束状态。转移规则用一张表来描述，代码里就是一个二维数组或者哈希表。这样写出来的代码虽然长，但逻辑清晰，边界条件一目了然。
def isNumber(s: str) -> bool: # 状态定义 # 0: 起始, 1: 符号, 2: 整数, 3: 小数点, 4: 小数, 5: 指数, 6: 指数符号, 7: 指数整数, 8: 结束 state = 0 for ch in s: if ch == ' ': if state == 0 or state == 8: continue else: return False elif ch in '+-': if state == 0 or state == 5: state += 1 else: return False elif ch.isdigit(): if state in (0, 1, 2): state = 2 elif state in (3, 4): state = 4 elif state in (5, 6, 7): state = 7 else: return False elif ch == '.': if state in (0, 1, 2): state = 3 else: return False elif ch in 'eE': if state in (2, 4): state = 5 else: return False else: return False return state in (2, 4, 7, 8)这段代码我精简过，实际写的时候状态转移表更完整。关键点在于：小数点只能出现在整数部分之后或者起始位置之后，指数符号只能出现在e之后，指数部分不能有小数点。这些规则用状态机表达出来，比用if-else堆砌要可靠得多。
实操心得：状态机写完后，一定要用测试用例覆盖所有边界。我常用的测试集包括："0"、" 0.1 "、"abc"、"1 a"、"2e10"、".1"、"1."、"."、"+"、"+.1"、"1e"、"e3"、".e3"、"6e-1"、"99e2.5"。其中"1."和".1"都是有效的，但"."是无效的，"1e"也是无效的。把这些都跑一遍，基本就能确认状态机没有漏洞。
3. 单词搜索II与柱状图最大矩形：字典树和单调栈的实战
3.1 单词搜索II：字典树加回溯，剪枝是关键
212题单词搜索II，给一个二维字符网格和一个单词列表，找出所有能在网格中通过相邻格子（上下左右）拼出来的单词。每个格子只能用一次，但不同单词之间可以重复使用格子。
最直观的做法是对每个单词单独做一次DFS，但这样时间复杂度是O(单词数 × 网格大小 × 单词长度)，单词一多就炸了。更好的做法是把所有单词建成一棵字典树，然后在网格上做一次DFS，同时沿着字典树往下走。这样只需要遍历网格一次，就能找到所有匹配的单词。
字典树的节点结构很简单：一个children字典或者数组，一个is_end标记。建树的时候把每个单词插入进去，DFS的时候从每个格子出发，如果当前字符在字典树当前节点的children里，就继续往下走，同时标记当前格子已访问，递归四个方向，最后回溯。
但这里有个大坑：如果单词列表里有很长的单词，而网格里根本没有对应的路径，DFS会做很多无用功。所以剪枝非常重要。我常用的剪枝策略有两个：一是如果字典树当前节点的children为空，直接返回；二是如果当前路径已经不可能形成任何单词（比如字典树节点没有子节点且不是单词结尾），也直接返回。
还有一个优化是“删除已找到的单词”。具体来说，当一个单词被找到后，把字典树里对应节点的is_end标记去掉，这样后续DFS就不会重复找到同一个单词。如果某个节点的所有子节点都被删除了，还可以把这个节点从父节点的children里移除，进一步减少搜索空间。
class TrieNode: def __init__(self): self.children = {} self.word = None class Solution: def findWords(self, board, words): # 建树 root = TrieNode() for w in words: node = root for ch in w: if ch not in node.children: node.children[ch] = TrieNode() node = node.children[ch] node.word = w result = [] rows, cols = len(board), len(board[0]) def dfs(i, j, node): ch = board[i][j] if ch not in node.children: return next_node = node.children[ch] if next_node.word: result.append(next_node.word) next_node.word = None # 去重 board[i][j] = '#' # 标记已访问 for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]: ni, nj = i + di, j + dj if 0 <= ni < rows and 0 <= nj < cols and board[ni][nj] != '#': dfs(ni, nj, next_node) board[i][j] = ch # 回溯 for i in range(rows): for j in range(cols): dfs(i, j, root) return result这段代码里，board[i][j] = '#'这个标记技巧很实用，比额外开一个visited数组要省空间。但要注意，如果网格里本来就有'#'字符，这个技巧会出问题，所以实际使用时要么用其他特殊字符，要么老老实实开visited数组。
常见问题：字典树节点用字典还是数组？如果字符集是26个小写字母，用长度为26的数组访问更快，但空间占用大；用字典更灵活，支持任意字符集。这道题明确说了只有小写字母，所以数组版本会更快，但字典版本代码更简洁。我一般面试时写字典版本，因为不容易出错。
3.2 柱状图最大矩形：单调栈的教科书案例
84题柱状图中最大的矩形，是单调栈的经典应用。题目给一个数组表示柱状图的高度，每个柱子宽度为1，求能勾勒出的最大矩形面积。
暴力解法是枚举左右边界，时间复杂度O(n²)，对于n=10^5的数据直接超时。单调栈的思路是：对于每个柱子，找到它左边第一个比它矮的柱子和右边第一个比它矮的柱子，这两个柱子之间的宽度乘以当前柱子的高度，就是以当前柱子为高的最大矩形面积。
为什么用单调栈？因为我们需要快速找到“左边第一个更小”和“右边第一个更小”的元素。单调递增栈正好能在O(n)时间内完成这个任务。具体操作：遍历每个柱子，当栈顶柱子的高度大于当前柱子高度时，说明栈顶柱子的右边界找到了，弹出栈顶，计算面积。计算面积时，左边界是弹出后新的栈顶（如果栈为空则左边界为-1），右边界是当前柱子索引。
def largestRectangleArea(heights): stack = [] max_area = 0 # 在末尾加一个0，确保所有柱子都能弹出 heights = heights + [0] for i, h in enumerate(heights): while stack and heights[stack[-1]] > h: height = heights[stack.pop()] width = i if not stack else i - stack[-1] - 1 max_area = max(max_area, height * width) stack.append(i) return max_area这里有个细节：为什么要在末尾加一个0？因为如果不加，遍历结束后栈里可能还有柱子没弹出，这些柱子的右边界就是数组末尾。加一个0可以强制所有柱子弹出，简化代码。这个技巧在单调栈题目里很常见，值得记住。
踩坑记录：我一开始写的时候忘了处理栈为空的情况，导致
stack[-1]报错。后来改成width = i if not stack else i - stack[-1] - 1，就对了。另外，宽度计算是i - stack[-1] - 1而不是i - stack[-1]，因为栈顶元素和当前元素之间隔了i - stack[-1] - 1个柱子。这个差一错误我犯了两次，每次都要画图才能确认。
4. 被围绕的区域与天际线问题：逆向思维和扫描线的碰撞
4.1 被围绕的区域：从边界反推比从内部正推更聪明
130题被围绕的区域，给一个二维棋盘，包含'X'和'O'，把所有被'X'完全包围的'O'变成'X'。注意，边界上的'O'以及和边界'O'连通的'O'不会被包围。
最直观的做法是遍历每个'O'，判断它是否被包围。但判断“是否被包围”本身就需要一次DFS，整体复杂度高。更好的做法是逆向思维：从边界上的'O'出发，把所有和边界'O'连通的'O'标记为安全，剩下的'O'就是被包围的，直接变成'X'。
这个思路的妙处在于，它把“判断是否被包围”这个复杂问题转化成了“从边界出发的连通性搜索”这个简单问题。实现上，先遍历四条边界，遇到'O'就做DFS，把连通的'O'标记成特殊字符（比如'#'）。然后遍历整个棋盘，把剩下的'O'变成'X'，把'#'变回'O'。
def solve(board): if not board or not board[0]: return rows, cols = len(board), len(board[0]) def dfs(i, j): if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != 'O': return board[i][j] = '#' dfs(i+1, j) dfs(i-1, j) dfs(i, j+1) dfs(i, j-1) # 从边界出发 for i in range(rows): dfs(i, 0) dfs(i, cols-1) for j in range(cols): dfs(0, j) dfs(rows-1, j) # 替换 for i in range(rows): for j in range(cols): if board[i][j] == 'O': board[i][j] = 'X' elif board[i][j] == '#': board[i][j] = 'O'这个解法的时间复杂度是O(mn)，空间复杂度是O(mn)（递归栈）。如果担心递归深度太大导致栈溢出，可以用BFS或者显式栈来替代递归。我实测下来，对于LeetCode的测试数据，递归版本完全够用，但如果棋盘特别大（比如1000x1000），还是建议用迭代版本。
注意事项：这道题和200题岛屿数量很像，但200题是数连通块个数，这道题是标记连通块并替换。两者的DFS框架几乎一样，区别在于对访问过的节点的处理方式。200题可以直接把访问过的'1'变成'0'来避免重复访问，这道题则需要用特殊字符标记，因为最后还要还原。
4.2 天际线问题：扫描线加优先队列，细节决定成败
218题天际线问题，给一组建筑物的左右边界和高度，求这些建筑物叠加后的天际线轮廓。输出是一组关键点，每个关键点表示天际线高度发生变化的位置。
这道题的经典解法是扫描线加最大堆。把所有建筑物的左右边界作为事件点，按x坐标排序。从左到右扫描，遇到左边界就把高度加入堆，遇到右边界就把高度从堆中移除（延迟删除）。每次扫描到一个事件点后，堆顶元素就是当前天际线的最大高度。如果这个高度和上一个关键点的高度不同，就记录一个新的关键点。
但这里有几个坑：一是堆里可能有已经失效的高度（建筑物已经结束），需要用延迟删除来处理；二是同一个x坐标可能有多个事件点，需要先处理所有左边界再处理右边界，否则会得到错误的天际线；三是输出格式要求相邻关键点高度不同，且最后一个关键点的高度必须是0。
import heapq def getSkyline(buildings): # 生成事件点 events = [] for left, right, height in buildings: events.append((left, -height, right)) # 左边界，负高度用于最大堆 events.append((right, height, 0)) # 右边界 events.sort(key=lambda x: (x[0], x[1])) result = [] heap = [(0, float('inf'))] # (负高度, 右边界) prev_height = 0 for x, neg_h, right in events: if neg_h < 0: # 左边界 heapq.heappush(heap, (neg_h, right)) else: # 右边界 # 延迟删除：不立即删除，等它到堆顶时再删 pass # 清理堆顶失效元素 while heap and heap[0][1] <= x: heapq.heappop(heap) curr_height = -heap[0][0] if curr_height != prev_height: result.append([x, curr_height]) prev_height = curr_height return result这段代码里，events.sort(key=lambda x: (x[0], x[1]))这个排序很关键。对于同一个x坐标，左边界（负高度）会排在右边界（正高度）前面，这样在同一个位置先处理左边界再处理右边界，保证天际线不会出现“先降后升”的错误。另外，堆里初始放一个(0, float('inf'))作为哨兵，避免堆为空时取堆顶报错。
实操心得：天际线问题的输出格式很容易出错。LeetCode要求返回的每个关键点是
[x, height]，且相邻关键点的height必须不同。我一开始忘了去重，导致输出里有连续相同高度的关键点，提交后报错。后来在添加关键点前加了if curr_height != prev_height的判断，就对了。另外，最后一个关键点的高度必须是0，因为天际线最终要回到地面。这个条件在代码里通过哨兵元素自然满足，不需要额外处理。
5. 六道题背后的通用刷题方法论
5.1 从“能过”到“优雅”的四个阶段
刷这六道题的过程中，我总结出一个Hard题的进阶路径，大概分四个阶段：
第一阶段是“能过就行”。不管时间复杂度，不管代码优雅度，先用最暴力的方法把题过了。这个阶段的目标是理解题意，确认自己的思路没有根本性错误。比如解数独，先用最朴素的回溯跑通，哪怕超时也没关系。
第二阶段是“优化到不超时”。分析暴力解法的瓶颈在哪里，用合适的数据结构去优化。解数独用布尔数组代替循环检查，单词搜索II用字典树代替逐个单词搜索，柱状图用单调栈代替双重循环。这个阶段的目标是把时间复杂度降到可接受的范围内。
第三阶段是“优化到优雅”。在能过的基础上，进一步压缩空间、简化代码、处理边界。比如解数独用位运算代替布尔数组，天际线问题用延迟删除代替实时删除。这个阶段的目标是让代码在面试中能拿高分。
第四阶段是“举一反三”。做完一道题后，思考它和哪些题相似，解法能不能迁移。比如被围绕的区域和岛屿数量都是连通性搜索，柱状图最大矩形和接雨水都是单调栈的应用。这个阶段的目标是建立知识网络，而不是孤立地刷题。
5.2 常见问题速查表
| 题目 | 常见错误 | 排查方法 | 修复方案 |
|---|---|---|---|
| 37 解数独 | 宫格索引计算错误 | 打印每个格子的宫格编号 | 用(i/3)*3 + j/3 |
| 65 有效数字 | 边界条件遗漏 | 用测试集覆盖所有情况 | 状态机完整定义 |
| 212 单词搜索II | 重复找到同一单词 | 检查结果列表是否有重复 | 找到后清除is_end标记 |
| 84 柱状图最大矩形 | 宽度计算差一 | 画图确认左右边界 | i - stack[-1] - 1 |
| 130 被围绕的区域 | 递归栈溢出 | 检查棋盘大小 | 改用BFS或显式栈 |
| 218 天际线问题 | 同一x坐标处理顺序错误 | 检查排序规则 | 左边界排在右边界前 |
5.3 刷题节奏与心态管理
这六道题我前后花了大概一周时间，平均每道题一天多。其中解数独和天际线问题花的时间最长，因为细节太多，每次提交都有新的报错。我的建议是：不要试图一天之内把六道Hard题全部搞定，那样只会让自己崩溃。每天集中精力攻克一道，做完后写一篇题解或者笔记，记录自己的思考过程和踩坑经历。第二天开始新题之前，先把昨天的题重新写一遍，确认自己真的掌握了，而不是当时看懂了。
另外，LeetCode周赛430里经常出现类似难度的题目，如果你能在周赛中稳定做出三道题，那这六道Hard题就是很好的训练材料。但如果你现在做中等题还很吃力，建议先回去巩固基础，不要硬啃Hard题。刷题不是比谁做的题多，而是比谁真正理解得深。
最后分享一个小技巧：每道Hard题做完后，去讨论区看看别人的解法。不是为了抄代码，而是为了看不同的思路。比如天际线问题，有人用分治做，有人用线段树做，虽然代码更复杂，但思路值得了解。我就是在讨论区里学会了用延迟删除处理堆的失效元素，这个技巧后来在别的题里也派上了用场。
6. 从这六道题延伸出去的知识网络
6.1 回溯类题目的通用模板
解数独、单词搜索II、被围绕的区域，本质上都是回溯或DFS。回溯类题目的通用模板是：定义状态、选择、撤销选择、判断终止条件。解数独的状态是当前盘面，选择是填1到9，撤销是清空格子；单词搜索II的状态是当前路径，选择是四个方向，撤销是标记回未访问；被围绕的区域的状态是当前连通块，选择是四个方向，撤销是还原字符。
掌握这个模板后，你可以轻松应对大多数回溯题。比如LeetCode 79单词搜索、46全排列、51N皇后，都是同一个框架。区别只在于状态的定义和剪枝的策略。
6.2 单调栈类题目的识别与套用
柱状图最大矩形是单调栈的入门题，但单调栈的应用远不止于此。接雨水、每日温度、下一个更大元素、最大矩形（二维版本），都是单调栈的变体。识别单调栈题目的关键是：题目是否要求找“左边/右边第一个更大/更小”的元素。如果是，那大概率可以用单调栈。
单调栈的代码模板很固定：遍历数组，维护一个单调递增或递减的栈，当当前元素破坏单调性时，弹出栈顶并计算结果。难点在于结果的计算方式，不同题目不一样。柱状图是计算面积，接雨水是计算水量，每日温度是计算距离。理解了这个模板，你就能举一反三。
6.3 扫描线类题目的适用场景
天际线问题是扫描线的经典应用，但扫描线的适用范围更广。凡是涉及“区间叠加”、“事件排序”、“动态维护最大值/最小值”的问题，都可以考虑扫描线。比如会议室安排、区间合并、矩形面积并等。
扫描线的核心是：把区间拆成事件点，按位置排序，然后从左到右扫描，用合适的数据结构维护当前状态。天际线问题用最大堆维护当前高度，矩形面积并用线段树维护覆盖长度。选择什么数据结构，取决于你需要维护什么信息。
这六道题刷完，你收获的不仅仅是六道题的解法，而是一整套分析问题、选择数据结构、优化代码的方法论。下次再遇到Hard题，你不会再感到恐惧，而是会兴奋地拆解它、攻克它。这才是刷题真正的意义。
