12 KiB
tags, create time
| tags | create time | |||
|---|---|---|---|---|
|
2026-05-17 09:30 |
21-搜索二维矩阵 II
题面
LeetCode 240. Search a 2D Matrix II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右 升序 排列。
- 每列的元素从上到下 升序 排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],
[3,6,9,16,22],[10,13,14,17,24],
[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],
[3,6,9,16,22],[10,13,14,17,24],
[18,21,23,26,30]], target = 20
输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-10^9 <= matrix[i][j] <= 10^9- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9
思路
[!question] 💡 直觉先行：这是一个有序矩阵，能不能用二分查找？
看到"有序"两个字，第一反应往往是 二分查找。但这里需要谨慎——这个矩阵的有序性是单向约束（每行递增、每列递增），而非全局有序。这意味着：
- 不能像普通数组那样对整张矩阵做二分。
- 每一行虽然自身有序，但行与行之间没有明确的界限关系。例如第 0 行末尾是
15，第 1 行开头是2（比15小）。所以无法排除某一整行来做二分。
[!danger] ⚠️ 一个常见的误区
有人可能会想："对每一行分别做二分查找"，即 O(m log n) 的方案。这在技术上是正确的，但不是最优解——题目给出的行列双向排序约束完全没有被利用。
让我们寻找一个能同时利用两个方向有序性的方法。
方法一：Z 字形搜索 —— 从右上角出发（O(m+n)）⭐⭐⭐
[!abstract] 🎯 核心洞察：每一步都能缩小搜索空间
[!question] 💡 如果你站在矩阵中的任意一个位置，能看到什么信息？
由于每行从左到右递增、每列从上到下递增，对于任意位置 (row, col)：
| 方向 | 大小关系 | 结论 |
|---|---|---|
| 右边 (col+1) | matrix[row][col+1] >= matrix[row][col] |
更大或相等 |
| 左边 (col-1) | matrix[row][col-1] <= matrix[row][col] |
更小或相等 |
| 下边 (row+1) | matrix[row+1][col] >= matrix[row][col] |
更大或相等 |
| 上边 (row-1) | matrix[row-1][col] <= matrix[row][col] |
更小或相等 |
关键问题是：选哪个起点能让我们在每一步都确定性地排除一行或一列？
[!tip] 🔑 起点选择规则
- 右上角 (0, n-1)：左侧是"更小"，下方是"更大"——恰好覆盖了我们比较
target后需要的两个方向。 - 左下角 (m-1, 0)：上方是"更小"，右侧是"更大"——同样可行。
- 左上角 ❌：右下都是更大的，无法缩小。
- 右下角 ❌：左上都是更小的，无法缩小。
[!step] Z 字形搜索流程
从右上角开始，根据比较结果决定移动方向：
flowchart TB
Start(["开始：定位右上角<br/>row=0, col=n-1"]) --> CheckBounds{"边界内？"}
CheckBounds -->|"否"| NotFound(["返回 false"])
CheckBounds -->|"是"| Compare["比较 target 与 matrix[row][col]"]
Compare -->|"相等"| Found(["返回 true ✅"])
Compare -->|"target 更大"| GoDown["当前值太小 → 向下走<br/>row++"]
Compare -->|"target 更小"| GoLeft["当前值太大 → 向左走<br/>col--"]
GoDown --> CheckBounds
GoLeft --> CheckBounds
[!example] 🔍 逐步跟踪演示
以 matrix 和 target = 5 为例，从右上角 (0, 4) = 15 开始：
| 步骤 | (row, col) | matrix[row][col] | 比较 | 动作 | 排除区域 |
|---|---|---|---|---|---|
| ① | (0, 4) | 15 |
5 < 15 |
左移 → col=3 | 排除第 4 列（下方都 ≥ 15） |
| ② | (0, 3) | 11 |
5 < 11 |
左移 → col=2 | 排除第 3 列 |
| ③ | (0, 2) | 7 |
5 < 7 |
左移 → col=1 | 排除第 2 列 |
| ④ | (0, 1) | 4 |
5 > 4 |
下移 → row=1 | 排除第 0 行（左侧都 ≤ 4） |
| ⑤ | (1, 1) | 5 |
5 == 5 |
找到了！ | — |
路径可视化（→ 表示搜索轨迹，✅ 表示找到）：
graph LR
subgraph M["矩阵视角"]
A["(0,4)=15<br/>↓ 左"] --> B["(0,3)=11<br/>↓ 左"]
B --> C["(0,2)=7<br/>↓ 左"]
C --> D["(0,1)=4<br/>↓ 下"]
D --> E["(1,1)=5<br/>✅ 找到!"]
end
[!note] 📌 为什么这个算法一定正确？
每一步我们要么把 row 加 1，要么把 col 减 1。在任何一步 (row, col)：
- 如果
target < matrix[row][col]，说明第col列中从row往下的所有元素都≥ matrix[row][col] > target，因此可以安全地排除第col列（col--）。 - 如果
target > matrix[row][col]，说明第row行中从col往左的所有元素都≤ matrix[row][col] < target，因此可以安全地排除第row行（row++）。
因为我们每次都排除了一整行或一整列，而最多只能排除 m + n 行/列之和的数量，所以循环一定会终止。
[!quote] ❌ 不用左上角或右下角的原因
想象从左上角 (0, 0) 开始——无论 target 比它大还是小：
target > matrix[0][0]：往下走还是往右走？两者都可能包含答案，无法做出确定性选择。target < matrix[0][0]：直接不可能存在（因为左上角最小）。
右下角同理可证。这就是为什么只有右上角和左下角这两个"对角"起点才合适——它们各有一侧是"只变小"，另一侧是"只变大"。
[!note] 📌 复杂度分析
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(m + n) | 每次排除一行或一列，最多走 m + n 步 |
| 空间 | O(1) | 只用两个指针变量 |
方法二：分治法（可选了解）
[!abstract] 🔄 递归分割思路
另一种思路是将矩阵沿对角线划分：取中间行 midRow，在该行做二分查找。若未找到：
target < matrix[midRow][midCol]：目标不可能出现在右上子矩阵（整块区域的值都大于 target），递归搜索其余三个子矩阵。target > matrix[midRow][midCol]：目标不可能出现在左下子矩阵。
平均情况下也是接近 O(m + n)，但常数因子较大且实现复杂。面试中推荐优先使用 Z 字形搜索。
代码提示
[!abstract] 📝 伪代码框架（Z 字形搜索）
// ── 从右上角出发 ──
row = 0
col = matrix[0] 的列数 - 1
while row < m 且 col >= 0:
if matrix[row][col] == target:
return true // 找到了！
if target > matrix[row][col]:
row++ // 当前值太小，往下走
else:
col-- // 当前值太大，往左走
return false // 走出边界，不存在
[!warning] ⚠️ 边界条件
- 空矩阵检查：当
matrix为空或某行为空时，直接返回false，避免越界。 - 循环终止条件：
row < m && col >= 0，任一条件不满足就停止。 - Go 中不需要特殊的切片处理，
len(matrix)和len(matrix[0])直接获取行列数。
技巧
[!tip] 🔑 核心模式：Z 字形搜索（Staircase Search / Saddleback Search）
当一个矩阵满足行递增 + 列递增的双向有序性时，从右上角或左下角出发的线性扫描是一条经典模式。每一步排除一行或一列，总步数不超过 m + n。
[!question] 💡 怎么判断是否适用这个模式？
检查矩阵的两个特征：
- 每行内部有序（递增或递减）
- 每列内部也有序，且方向与行相同
两个条件同时满足时，Z 字形搜索就是首选方案。
[!note] 🐹 Go 语言中的注意事项
- Go 的
len(matrix)返回行数，len(matrix[0])返回列数。注意先做空切片检查再取matrix[0]，否则空矩阵会 panic。 - 双索引滑动在 Go 中用简单的
for循环最自然。 - 布尔返回值
bool在 Go 中默认值为false，所以最后直接return false即可。
[!info] 📊 与其他搜索方法的对比
| 方法 | 时间复杂度 | 空间 | 是否需要完全有序 | 适用条件 |
|---|---|---|---|---|
| Z 字形搜索 | O(m + n) | O(1) | ❌ 仅需行/列各自有序 | 本题场景 ✅ |
| 逐行二分 | O(m log n) | O(1) | ❌ 仅需行有序 | 行数远小于列数时可用 |
| 整体二分（压平） | O(log(mn)) | O(1) | ✅ 需要全局有序 | 如 LeetCode 74（每行首元素 > 上一行末元素） |
| 暴力遍历 | O(mn) | O(1) | ❌ 无需有序 | 无序矩阵的唯一选择 |
[!quote] 💬 思维延伸：对角线的力量
这道题揭示了一个优雅的算法设计原则：
不要试图一次性看到全局最优解，而是让每个局部决策都"排除一大片"。
Z 字形搜索每一步排除一行或一列，看似简单，实则暗含了"单调性导航"的思想——你不需要知道目标确切在哪里，只需要在每个路口做一个二选一的决定，就能把搜索空间以线性速度缩减。
这种思想也出现在：
- **杨氏矩阵（Young Tableau）**中的删除操作：从右上角出发，每次交换并继续搜索剩余子矩阵。
- 两个有序数组的中位数问题：在两个有序数组上做交叉二分。
- 旋转数组搜索：通过判断一半区间是否有序来排除。
记住这个模式：「排序矩阵 + 从对角出发 = 每一步排除一行/列」，下次遇到类似问题可以直接调用。
代码
// searchMatrix 在一个行递增、列递增的 m x n 矩阵中搜索 target。
// 使用 Z 字形搜索（从右上角出发），时间 O(m+n)，空间 O(1)。
func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
// ═══ 边界检查：空矩阵直接返回 false ═══
if m == 0 || n == 0 {
return false
}
// ═══ 从右上角开始 Z 字形搜索 ═══
row := 0 // 起始行：第 0 行
col := n - 1 // 起始列：最后一列（右上角）
for row < m && col >= 0 {
cur := matrix[row][col]
if cur == target {
return true // 找到目标，返回 true
}
if target > cur {
row++ // target 比当前值大：往下走（下一行有更大值）
} else {
col-- // target 比当前值小：往左走（前一列有更小值）
}
}
// 走出边界仍未找到
return false
}
[!success] ✅ 运行验证
这是 LeetCode 第 240 题，通过率约 47%，是一道经典的 有序矩阵搜索面试题。
- 运行时间：约 0~4 ms（Go，击败 ~95%+ 提交）
- 空间消耗：O(1) 额外空间
- 面试表现：极高。面试官最常追问的问题：
- 为什么不能从左上角或右下角出发？（那一点的两个方向都"增大"或都"减小"，无法做出确定性选择）
- 时间复杂度为什么是 O(m+n) 而不是 O(m×n)？（每一步排除一整行或一整列，最多 m+n 步）
- 这个方法能扩展到矩阵中存在重复元素的情况吗？（能——去重不影响有序性保证）
- 如果矩阵极大（比如 10^5 × 10^5），还有什么优化方向？（可以考虑对每行做二分 O(m log n)，或者结合分治+二分近似 O((m+n)/2 * log(...))）
[!quote] 💬 延伸思考
这道题的精妙之处在于，它利用矩阵的偏序结构（partial order）——我们知道每行内部、每列内部的顺序关系，但不知道跨行或跨列的全局大小关系。Z 字形搜索正是"偏序导航"的最优策略：在不丢失正确性的前提下，用最少步数探明目标是否存在。
当你下次面对"部分有序的结构"时，回想这个 Z 字形模板：找到那个"一个方向变小、另一个方向变大"的锚点，然后顺着它的指引走下去。