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) ? 最優

這個算法充分利用了矩陣的有序性質，是一個經典的"減治"思想的體現。