298 lines
12 KiB
Markdown
298 lines
12 KiB
Markdown
---
|
||
tags: ["LeetCode", "矩阵", "中等"]
|
||
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.length`
|
||
- `n == matrix[i].length`
|
||
- `1 <= 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 字形搜索流程
|
||
|
||
从右上角开始，根据比较结果决定移动方向：
|
||
|
||
```mermaid
|
||
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` | **找到了！** | — |
|
||
|
||
路径可视化（`→` 表示搜索轨迹，`✅` 表示找到）：
|
||
|
||
```mermaid
|
||
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] ⚠️ 边界条件
|
||
|
||
1. **空矩阵检查**：当 `matrix` 为空或某行为空时，直接返回 `false`，避免越界。
|
||
2. **循环终止条件**：`row < m && col >= 0`，任一条件不满足就停止。
|
||
3. Go 中不需要特殊的切片处理，`len(matrix)` 和 `len(matrix[0])` 直接获取行列数。
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：Z 字形搜索（Staircase Search / Saddleback Search）
|
||
|
||
当一个矩阵满足**行递增 + 列递增**的双向有序性时，从**右上角**或**左下角**出发的线性扫描是一条经典模式。每一步排除一行或一列，总步数不超过 `m + n`。
|
||
|
||
> [!question] 💡 怎么判断是否适用这个模式？
|
||
|
||
检查矩阵的两个特征：
|
||
1. **每行内部有序**（递增或递减）
|
||
2. **每列内部也有序**，且方向与行相同
|
||
|
||
两个条件同时满足时，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）**中的删除操作：从右上角出发，每次交换并继续搜索剩余子矩阵。
|
||
- **两个有序数组的中位数**问题：在两个有序数组上做交叉二分。
|
||
- **旋转数组搜索**：通过判断一半区间是否有序来排除。
|
||
|
||
记住这个模式：**「排序矩阵 + 从对角出发 = 每一步排除一行/列」**，下次遇到类似问题可以直接调用。
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
// 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 字形模板：**找到那个"一个方向变小、另一个方向变大"的锚点，然后顺着它的指引走下去。**
|