LeetCode hot 100 每日一题(16)——240. 搜索二维矩阵 II

这是一道难度为中等的题目，让我们来看看题目描述：

编写一个高效的算法来搜索 _m_ x _n_ 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -$10^9$ <= matrix[i][j] <= $10^9$
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -$10^9$ <= target <= $10^9$

题解

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 获取矩阵的行数 (m) 和列数 (n)
        int m = matrix.length;
        int n = matrix[0].length;

        // 从矩阵的右上角开始搜索
        int i = 0;      // 行索引，从第 0 行开始
        int j = n - 1;  // 列索引，从最后一列开始

        // 进行搜索，直到越界
        while (i < m && j >= 0) {
            // 如果当前元素等于目标值，返回 true
            if (matrix[i][j] == target) {
                return true;
            }

            // 如果当前元素小于目标值，向下移动 (增加行索引)
            if (matrix[i][j] < target) {
                i++;
            } 
            // 如果当前元素大于目标值，向左移动 (减少列索引)
            else {
                j--;
            }
        }

        // 遍历完都没找到目标值，返回 false
        return false;
    }
}

思路

给定一个 m × n 的二维矩阵，矩阵满足：

• 每行的元素从左到右 单调递增

• 每列的元素从上到下 单调递增

目标是在该矩阵中查找是否存在某个 target 值，并返回 true 或 false。

由于矩阵具有 行列单调递增 的特性，可以利用 从右上角开始查找 的策略：

1. 初始化 位置：

   • 从矩阵的 右上角 ( matrix[0][n-1] ) 开始

   • 这个位置的值是当前行的最大值，当前列的最小值

2. 查找策略：

   • 如果当前元素等于 target，直接返回 true

   • 如果当前元素 小于 target，说明 target 可能在更 下面的行，向 下移动

   • 如果当前元素 大于 target，说明 target 可能在更 左侧的列，向 左移动

   • 这样每次移动都会缩小搜索范围，直到找到 target 或者超出边界

3. 终止条件：

   • 如果行索引 i 超出 m 或者列索引 j 变成负数，说明矩阵中不存在 target，返回 false

时间 & 空间复杂度分析

• 时间复杂度: O(m + n)

  • 最坏情况下，从右上角走到左下角，总共 m + n - 1 步

• 空间复杂度: O(1)

  • 只使用了常数级别的额外空间

总结：

• 这种 “步步逼近” 的方法比直接 O(m*n) 遍历要快得多

• 由于每次移动都会缩小搜索空间，效率很高

• 适用于大规模 m, n 的情况下