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 152  5  8 12 193  6  9 16 22
10 13 14 17 24
18 21 23 26 30

搜索过程演示：

步骤	当前位置	当前值	比较结果	操作	说明
1	(0,4)	15	15 > 5	向左移动	排除第4列
2	(0,3)	11	11 > 5	向左移动	排除第3列
3	(0,2)	7	7 > 5	向左移动	排除第2列
4	(0,1)	4	4 < 5	向下移动	排除第0行
5	(1,1)	5	5 = 5	找到！	返回true

步骤可视化：

步骤1: 从右上角开始

 1  4  7 11 [15] ← 起始位置2  5  8 12  193  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	(0,4)	15	15 < 20	向下移动	排除第0行
2	(1,4)	19	19 < 20	向下移动	排除第1行
3	(2,4)	22	22 > 20	向左移动	排除第4列
4	(2,3)	16	16 < 20	向下移动	排除第2行
5	(3,3)	17	17 < 20	向下移动	排除第3行
6	(4,3)	26	26 > 20	向左移动	排除第3列
7	(4,2)	23	23 > 20	向左移动	排除第2列
8	(4,1)	21	21 > 20	向左移动	排除第1列
9	(4,0)	18	18 < 20	向下移动	越界，未找到

步骤可视化：

步骤1: 从右上角开始

 1  4  7 11 [15] ← 起始位置，15 < 202  5  8 12  193  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) ✓ 最优

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