LeetCode 第 240 题：搜索二维矩阵 II

题目描述
给定一个 m x n 的二维矩阵 matrix，该矩阵具有以下特性：

• 每行中的整数从左到右按升序排列。
• 每列中的整数从上到下按升序排列。

要求编写一个高效的算法来搜索目标值 target。如果 target 存在于矩阵中，返回 true；否则返回 false。

例如：

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
target = 20 → 返回 false

解题过程

1. 问题分析
矩阵的每行和每列都是有序的，但整体并非完全有序（例如，下一行的第一个元素不一定大于上一行的最后一个元素）。因此不能直接套用标准的二分查找。需要利用局部有序性设计搜索路径。

2. 关键观察
从矩阵的右上角（或左下角）开始搜索：

• 如果从右上角开始：
  • 当前元素等于 target → 找到目标，返回 true。
  • 当前元素大于 target → 由于列是升序，当前列下方的元素都更大，因此可以排除当前列，向左移动一列。
  • 当前元素小于 target → 由于行是升序，当前行左侧的元素都更小，因此可以排除当前行，向下移动一行。
• 这样每一步都能排除一行或一列，逐步缩小搜索范围。

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. 举例说明
以示例矩阵搜索 target=5 为例：

• 初始位置 (0,4)：值 15 > 5，左移列 → (0,3)：值 11 > 5，左移 → (0,2)：值 7 > 5，左移 → (0,1)：值 4 < 5，下移行 → (1,1)：值 5 == 5，找到目标。

5. 复杂度分析

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

6. 为什么选择右上角/左下角？
因为这两个位置具有“方向性”：右上角向左变小、向下变大；左下角向右变大、向上变小。这种单调性确保了每一步移动都能明确排除一部分区域，而其他角落（如左上或右下）不具备这种性质。