---
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 字形模板：**找到那个"一个方向变小、另一个方向变大"的锚点，然后顺着它的指引走下去。**