LeetCode 240: 搜索二维矩阵 II - 算法详解(秒懂系列

LeetCode 240: 搜索二维矩阵 II - 算法详解

题目描述

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

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

Java解决方案

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 从右上角开始搜索
        int row = 0;
        int col = matrix[0].length - 1;
        
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) {
                return true; // 找到目标值
            } else if (matrix[row][col] > target) {
                col--; // 当前值大于目标，向左移动
            } else {
                row++; // 当前值小于目标，向下移动
            }
        }
        
        return false; // 未找到目标值
    }
}

算法思路

核心理念

利用矩阵的有序特性，从右上角（或左下角）开始搜索，可以在每一步确定性地排除一整行或一整列。

为什么选择右上角？

• 右上角特性：当前元素是所在行的最大值，同时是所在列的最小值
• 决策明确：
  • 如果当前值 > target，可以排除整列（向左移动）
  • 如果当前值 < target，可以排除整行（向下移动）

可视化演示过程

示例1：查找 target = 5

初始矩阵：

 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

搜索过程演示：

步骤可视化：

步骤1: 从右上角开始

 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

步骤2: 向左移动

 1  4  7 [11] ×   ← 15 > 5, 向左移动
 2  5  8 12  ×
 3  6  9 16  ×
10 13 14 17  ×
18 21 23 26  ×

步骤3: 继续向左移动

 1  4 [7] ×   ×   ← 11 > 5, 向左移动
 2  5  8  ×   ×
 3  6  9  ×   ×
10 13 14  ×   ×
18 21 23  ×   ×

步骤4: 再次向左移动

 1 [4] ×  ×   ×   ← 7 > 5, 向左移动
 2  5  ×  ×   ×
 3  6  ×  ×   ×
10 13  ×  ×   ×
18 21  ×  ×   ×

步骤5: 向下移动找到目标

 ×  ×  ×  ×   ×   ← 4 < 5, 向下
 2 [5] ×  ×   ×   ← 找到目标！
 3  6  ×  ×   ×
10 13  ×  ×   ×
18 21  ×  ×   ×

示例2：查找 target = 20 (不存在)

搜索过程演示：

步骤可视化：

步骤1: 从右上角开始

 1  4  7 11 [15] ← 起始位置，15 < 20
 2  5  8 12  19
 3  6  9 16  22
10 13 14 17  24
18 21 23 26  30

步骤2: 向下移动

 ×  ×  ×  ×   ×   ← 排除第0行
 2  5  8 12 [19] ← 19 < 20，继续向下
 3  6  9 16  22
10 13 14 17  24
18 21 23 26  30

步骤3: 继续向下移动

 ×  ×  ×  ×   ×   ← 排除第0行
 ×  ×  ×  ×   ×   ← 排除第1行  
 3  6  9 16 [22] ← 22 > 20，向左移动
10 13 14 17  24
18 21 23 26  30

步骤4: 向左移动后向下

 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   ← 排除第2行
10 13 14 [17] ×   ← 17 < 20，向下移动
18 21 23  26  ×

步骤5: 继续向下移动

 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   ← 排除第3行
18 21 23 [26] ×   ← 26 > 20，向左移动

步骤6-8: 连续向左移动

步骤6:
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
18 21 [23] ×  ×   ← 23 > 20，向左

步骤7:
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
18 [21] ×  ×  ×   ← 21 > 20，向左

步骤8:
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
[18] ×  ×  ×  ×   ← 18 < 20，向下

步骤9: 尝试向下移动，越界

 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   
 ×  ×  ×  ×   ×   ← 所有位置都被排除
[越界] ← row >= matrix.length，搜索结束

最终结果： 返回 false

算法分析

时间复杂度

• O(m + n) - 其中 m 是行数，n 是列数
• 最坏情况下需要遍历一行加一列的长度

空间复杂度

• O(1) - 只使用常量额外空间

算法优势

1. 高效性：时间复杂度优于暴力搜索O(mn)
2. 简洁性：代码逻辑清晰，易于理解
3. 最优性：这是该问题的最优解法之一

关键要点

1. 起始位置选择：右上角或左下角都可以，但不能选择左上角或右下角
2. 决策准则：利用有序性质，每步都能排除一行或一列
3. 边界处理：注意数组越界检查

扩展思考

1. 为什么不能从左上角开始？

   • 左上角是行最小值和列最小值，无法确定移动方向

2. 左下角算法：

   int row = matrix.length - 1;
   int col = 0;
   // 大于target向上，小于target向右
   

3. 其他解法对比：

   • 每行二分查找：O(m log n)
   • 暴力搜索：O(mn)
   • 右上角搜索：O(m + n) ✓ 最优

这个算法充分利用了矩阵的有序性质，是一个经典的"减治"思想的体现。