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

题目描述

给定一个 m x n 的矩阵 matrix，该矩阵具有以下特性：

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

请编写一个高效的算法，来搜索该矩阵中是否存在一个目标值 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

输入：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

解题过程

第一步：理解问题与数据特性

首先，我们不能简单地将其视为一个普通二维数组进行暴力搜索（时间复杂度 O(m*n)），因为题目要求“高效”的算法。关键在于利用题目给出的两个有序特性：

1. 行有序：每一行都是一个从左到右递增的序列。
2. 列有序：每一列都是一个从上到下递增的序列。

这个特性意味着，对于矩阵中的任意一个元素 matrix[i][j]：

• 它左边的所有元素（matrix[i][0..j-1]）都比它小。
• 它下边的所有元素（matrix[i+1..m-1][j]）都比它大。
• 它右边的所有元素（matrix[i][j+1..n-1]）都比它大。
• 它上边的所有元素（matrix[0..i-1][j]）都比它小。

这种局部有序性为我们提供了优化的搜索路径。

第二步：寻找搜索起点

一个直观的想法是，如果我们能从一个“角落”开始搜索，利用大小关系每次排除掉一行或一列，就能快速缩小搜索范围。有四个角落可供选择：

1. 左上角 (0, 0)：该元素是全局最小值。向右和向下移动，元素都变大。如果我们从左上角开始，不知道应该向右走还是向下走才能接近目标，没有明确的排除方向。
2. 右下角 (m-1, n-1)：该元素是全局最大值。向左和向上移动，元素都变小。同样，不知道应该向左走还是向上走，没有明确的排除方向。
3. 左下角 (m-1, 0)：这个点非常关键。对于这个元素：
   • 它上方的所有元素都比它小。
   • 它右方的所有元素都比它大。
   • 这构成了一个明确的“搜索阶梯”。我们可以将当前元素 curr 与目标 target 比较：
     • 如果 curr == target，找到目标，返回 true。
     • 如果 curr < target，说明目标值比当前元素大。根据特性，目标值不可能出现在当前元素的左边（左边更小）或上方（上方更小），只可能出现在当前元素的右边。因此，我们可以排除当前列，将搜索位置向右移动一列（j++）。
     • 如果 curr > target，说明目标值比当前元素小。根据特性，目标值不可能出现在当前元素的下边（下边更大）或右边（右边更大），只可能出现在当前元素的上方。因此，我们可以排除当前行，将搜索位置向上移动一行（i--）。
4. 右上角 (0, n-1)：与左下角同理，只是移动方向相反。
   • 如果 curr == target，返回 true。
   • 如果 curr < target，说明目标值更大，排除当前行，向下移动（i++）。
   • 如果 curr > target，说明目标值更小，排除当前列，向左移动（j--）。

第三步：算法步骤（以从右上角开始为例）

1. 初始化：设置两个指针（或索引）。row 指向第一行（0），col 指向最后一列（n-1）。这样我们就定位到了右上角的元素。
2. 循环搜索：在 row 小于总行数（m）且 col 大于等于 0 的范围内进行循环。
   a. 获取当前元素 current = matrix[row][col]。
   b. 比较 current 和 target：
   * 如果 current == target，搜索成功，返回 true。
   * 如果 current < target：意味着目标值肯定不在当前这一行（因为当前是这一行最大的数，它都比目标小），所以我们可以排除整行。将 row 加一（向下移动），进入下一行。
   * 如果 current > target：意味着目标值肯定不在当前这一列（因为当前是这一列最小的数，它都比目标大），所以我们可以排除整列。将 col 减一（向左移动），进入前一列。
3. 终止条件：如果循环结束（即 row 越过了矩阵底部或 col 越过了矩阵左边界）还没有找到目标值，说明目标值不存在于矩阵中，返回 false。

第四步：复杂度分析

• 时间复杂度：O(m + n)。在最坏的情况下，我们从右上角走到左下角，比如先走到最左边（col 从 n-1 减到 0），再走到最下边（row 从 0 加到 m-1），总共遍历了 m + n 个元素。这是一个非常高效的时间复杂度。
• 空间复杂度：O(1)。我们只使用了几个额外的变量（row, col），是常数级别的空间消耗。

第五步：举例说明

以示例一 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 为例，从右上角 (0,4) 开始：

1. (0,4): 15 > 5 -> 太大，排除第4列，col-- -> (0,3)
2. (0,3): 11 > 5 -> 太大，排除第3列，col-- -> (0,2)
3. (0,2): 7 > 5 -> 太大，排除第2列，col-- -> (0,1)
4. (0,1): 4 < 5 -> 太小，排除第0行，row++ -> (1,1)
5. (1,1): 5 == 5 -> 找到目标，返回 true。

可以看到，我们并没有遍历所有元素，而是通过巧妙的比较和移动，快速定位到了目标。