LeetCode 240. 搜索二维矩阵 II

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。

这个矩阵具有以下特性：

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

• 每列的元素从上到下升序排列

现在要判断目标值 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

因为矩阵中确实存在数字 5。

示例 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

因为矩阵中不存在 20。

解题思路

这道题最重要的不是代码本身，而是找到一个合适的“起点”。

因为这个矩阵有两个排序性质：

1. 每一行从左到右递增

2. 每一列从上到下递增

如果我们随便选一个位置开始，比如左上角或者右下角，其实并不能很好地利用这两个性质。

但如果从左下角或者右上角开始，就很巧妙了。

你给出的代码就是从左下角开始搜索：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while(i >= 0 && j < matrix[0].length)
        {
            if(matrix[i][j] > target) i--;
            else if(matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }
}

这是一种非常经典的做法，时间复杂度可以做到：

O(m + n)

为什么从左下角开始

假设当前我们站在矩阵的左下角位置 (i, j)。

这个位置有两个非常重要的特点：

• 它右边的元素都比它大（因为这一行递增）

• 它上边的元素都比它小（因为这一列递增）

也就是说，在左下角这个点：

• 往右走，数字会变大

• 往上走，数字会变小

这就给了我们明确的决策方向。

如何根据当前值移动

假设当前值是：

matrix[i][j]

情况 1：当前值大于 target

如果：

matrix[i][j] > target

因为当前列从上到下递增，而我们现在已经在这一列的最下面。

所以当前值已经比目标大了，那么这一列中当前行以上才可能有更小的值。

这时正确做法就是：

往上走一行

也就是：

i--;

因为往上走，值会变小，才有可能接近目标。

情况 2：当前值小于 target

如果：

matrix[i][j] < target

由于当前行从左到右递增，而我们现在已经在这一行最左边。

当前位置已经比目标小了，那么这一行中只有右边才可能出现更大的值。

这时正确做法就是：

往右走一列

也就是：

j++;

因为往右走，值会变大，才有可能接近目标。

情况 3：当前值等于 target

直接返回：

return true;

为什么每一步都能排除一部分区域

这是这道题最关键的地方。

当当前值大于 target 时

我们选择向上移动：

i--;

因为：

• 当前值已经太大

• 当前值右边的元素更大

• 所以当前位置以及它右边的区域都不可能是答案

这一步相当于排除掉了当前行的一部分搜索空间。

当当前值小于 target 时

我们选择向右移动：

j++;

因为：

• 当前值已经太小

• 当前值上边的元素更小

• 所以当前位置以及它上方的区域都不可能是答案

这一步相当于排除掉了当前列的一部分搜索空间。

为什么左上角和右下角不适合做起点

很多同学第一次做这题时，会想从左上角开始。

比如左上角是最小值：

• 如果它比 target 小，我们只能往右或者往下

• 但这两个方向都会变大，无法确定应该选哪一个

同样，右下角是最大值：

• 如果它比 target 大，我们只能往左或者往上

• 这两个方向都会变小，也无法确定该往哪边走

所以左上角和右下角都没有“唯一决策方向”。

而左下角和右上角则有。

这也是为什么这题的标准做法通常都是：

• 从左下角开始

• 或从右上角开始

代码解析

1. 初始化左下角位置

int i = matrix.length - 1, j = 0;

• i = matrix.length - 1：最后一行

• j = 0：第一列

这正好就是左下角。

2. 只要没有越界，就继续查找

while(i >= 0 && j < matrix[0].length)

• i >= 0：说明还没有越过最上面

• j < matrix[0].length：说明还没有越过最右边

只要还在矩阵范围内，就继续比较。

3. 当前值大于目标，往上走

if(matrix[i][j] > target) i--;

因为当前位置太大，只能往上找更小的值。

4. 当前值小于目标，往右走

else if(matrix[i][j] < target) j++;

因为当前位置太小，只能往右找更大的值。

5. 当前值等于目标

else return true;

找到答案，直接返回 true。

6. 走出矩阵还没找到

return false;

说明整个搜索过程已经结束，目标值不存在。

示例推演

还是看这个矩阵：

[
  [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

第一步：从左下角开始

当前位置：

18

比较：

18 > 5

说明太大，往上走。

第二步

当前位置：

10

比较：

10 > 5

继续往上走。

第三步

当前位置：

3

比较：

3 < 5

说明太小，往右走。

第四步

当前位置：

6

比较：

6 > 5

往上走。

第五步

当前位置：

5

找到了，返回 true。

为什么时间复杂度是 O(m + n)

在搜索过程中，每一步只会做两种操作之一：

• 往上走一格

• 往右走一格

而：

• 最多往上走 m 次

• 最多往右走 n 次

所以总步数不会超过：

m + n

因此时间复杂度就是：

O(m + n)

这比暴力遍历整个矩阵的 O(m * n) 要高效得多。

复杂度分析

假设矩阵大小为 m x n。

时间复杂度

O(m + n)

空间复杂度

O(1)

只使用了两个下标变量，没有额外空间。

和暴力解法对比

暴力解法

思路：

• 遍历矩阵中每一个元素

• 判断是否等于 target

优点：

• 简单直接

缺点：

• 时间复杂度是 O(m * n)

• 没有利用矩阵的有序性

当前这种“左下角搜索”做法

优点：

• 充分利用了行列递增的性质

• 时间复杂度优化到 O(m + n)

• 实现简洁

缺点：

• 第一次接触时，不太容易想到“从左下角开始”

总结

这道题的核心就在于选对起点。

因为左下角这个位置具有非常特殊的性质：

• 向右变大

• 向上变小

所以每次比较后，我们都能明确知道下一步该往哪走：

1. 当前值大于目标，往上

2. 当前值小于目标，往右

3. 当前值等于目标，返回 true

你可以把这题记成一句话：

从左下角出发，大了往上，小了往右。

这是一道非常经典的二维矩阵搜索题，只要把“为什么左下角有唯一决策方向”这个点想明白，这道题就彻底掌握了。