LeetCode 第 240 题：搜索二维矩阵 II（Search a 2D Matrix II）

题目描述
编写一个高效的算法来搜索 m x n 矩阵中的一个目标值。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

例如：

矩阵：
[
  [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]
]
目标值：5，返回 true；目标值 20，返回 false。

解题思路

步骤 1：理解矩阵特性

• 矩阵并非完全有序（例如右下角可能大于左上角），但每行递增、每列递增。
• 暴力遍历所有元素（时间复杂度 O(mn)）效率低，需利用特性优化。

步骤 2：观察规律

从矩阵的右上角（或左下角）开始：

• 若当前值等于目标值，直接返回 true。
• 若当前值大于目标值，说明目标值不可能在当前列（因为当前列下方的值更大），向左移动一列。
• 若当前值小于目标值，说明目标值不可能在当前行（因为当前行左侧的值更小），向下移动一行。

这样每一步都能排除一行或一列，逐步缩小搜索范围。

步骤 3：算法流程

1. 初始化指针到右上角：row = 0, col = n - 1。
2. 当 row < m 且 col >= 0 时循环：
   • 如果 matrix[row][col] == target，返回 true。
   • 如果 matrix[row][col] > target，col--（向左移）。
   • 如果 matrix[row][col] < target，row++（向下移）。
3. 循环结束未找到目标值，返回 false。

步骤 4：举例演示

以目标值 5 为例：

初始位置：右上角 15 (0,4)
15 > 5 → 左移 col=3 → 值 11
11 > 5 → 左移 col=2 → 值 7
7 > 5 → 左移 col=1 → 值 4
4 < 5 → 下移 row=1 → 值 5（找到目标）

步骤 5：复杂度分析

• 时间复杂度：O(m + n)。最坏情况下从右上角走到左下角。
• 空间复杂度：O(1)。仅使用常数级额外空间。

关键点

• 利用矩阵的局部有序性，从右上角或左下角开始搜索，避免全局遍历。
• 类似“步步逼近”的策略，每次排除一行或一列。