矩阵
01 / 共享的机制
矩阵不是一条线性序列,而是一片二维坐标空间 —— 每个格子由两个下标共同决定, 二者按某种方式组合在一起。关键在于找到正确的「走法」。 三个经典子模式:原地旋转(转置 + 行翻转)、螺旋遍历(四条边界向内收缩)、阶梯搜索(从某个角出发,该角上一方向单调递增另一方向单调递减)。
01 / 一句话本质
从右上角出发。把当前格子和目标比较,要么往左走(整列都太大), 要么往下走(整行都太小)。每一步淘汰一整行或一整列, 于是总耗时O(R + C),不再是O(R · C)。
题目在行列均有序矩阵中查找 targetR×C3×3target5
矩阵规模 3×3。从右上角 (0, 2) 出发。目标 5。
步
0 / 6
i
0
j
2
状态
查找中
0 / 6
02 / 模式骨架
# 从右上角开始;行列均按升序排列i ← 0; j ← C − 1while i < R and j ≥ 0:if mat[i][j] == target: return (i, j)elif mat[i][j] > target: j ← j − 1 # 整列偏大,淘汰else: i ← i + 1 # 整行偏小,淘汰return (−1, −1) # 走出网格
03 / 什么时候用这个模式
"行列都已排序的矩阵中查找"
LC 240 —— Search a 2-D Matrix II 的标准用法。每一行从左到右递增,每一列从上到下递增, 但行尾和下一行行首没有大小关系。这种情形下,阶梯搜索是正确解法,二分查找不行。
"每行已排序、且下一行首大于上一行末"
LC 74 —— 看着像但其实是陷阱姐妹题。多出的“行尾接行首”约束, 让整个矩阵等价于一条排好序的数组 —— 直接对
R · C 个下标做二分,O(log(R · C)) 比阶梯快。看清排序结构,而不是只看维度。"有序矩阵中第 K 小元素"
LC 378 —— 行列单调的结构不变,问题换成了排名而非存在性。阶梯走法可以推广: 从一个角出发,以
O(R + C) 数出有多少格子 ≤ x,然后对 x 二分。"在有序网格中统计满足某性质的对数"
只要二维网格有「一个方向值单调增、另一方向值单调减」的性质, 一趟阶梯走就能扫过所有边界格子。在两条有序数组里统计满足
A[i] + B[j] < T 的对数 (i, j) 也是同一形状。04 / 常见坑
i.
从左上或右下角出发。
这两个角是全矩阵的最小或最大值 —— 两个邻居都朝同一方向走(都更大或都更小), 一次比较没法区分应该退哪个轴。只有右上和左下具备“一个邻居更大、一个邻居更小”的性质, 阶梯才走得起来。
ii.
把 LC 74(行尾接行首)和 LC 240(行列独立单调)混为一谈。
LC 74 保证下一行首元素大于上一行末元素,矩阵被压扁成一条有序数组, 正确工具是把
R · C 个下标当数组做二分。LC 240 只保证行有序且列有序, 行尾和下一行的关系没有任何承诺 —— 这就把工具逼到阶梯搜索。看约束,不要光看图。iii.
忘记在
i == R 或 j < 0 时退出循环。走出顶部或右边界时,目标不在矩阵里 —— 直接返回
(−1, −1)(或 false)。 只检查一个边界、或对列下标差一,要么漏掉最后一列里的答案,要么访问越界。 每次迭代都必须同时守住 i < R 与 j ≥ 0。05 / 去 LeetCode 上练习
四道题。第一道是教科书阶梯走;第二道是“长得像但应该用二分”的陷阱; 后两道把同样的行列单调结构挪去做排名和计数。
— / 什么时候用哪个
原地旋转
题目要做的是网格本身的几何变换 —— 90° / 180° 旋转、转置、镜像时使用。 拆成两步(转置 + 行翻转)就能原地完成,不需要新的网格。
转置 + 翻转 · LC 48
螺旋遍历
需要按外圈顺序访问每个格子 —— 螺旋输出、螺旋填充、统计层数时使用。 维护四条边界,每走完一圈就把它们向内收缩。
四条边界 · LC 54 · LC 59
阶梯搜索
矩阵行列都单调且要查找一个值时使用。从一个「一方向递增、另一方向递减」的角出发, 每次比较都能淘汰整行或整列。
右上角出发 · LC 240 · O(N + M)