【力扣100题】25. 搜索二维矩阵 II

一、题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 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

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

提示：

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

二、解题思路总览

核心思想：从右上角开始，利用有序性单向剪枝

从矩阵的右上角开始搜索，每次比较后根据大小关系排除一行或一列：

• 如果当前元素大于 target，说明目标不可能在当前列的下方，往左走
• 如果当前元素小于 target，说明目标不可能在当前行的上方，往下走

为什么从右上角或左下角开始？

因为这两个角具有「单向有序」的特性：

• 右上角：同行左边更小，同列下边更大
• 左下角：同行右边更大，同列上边更小

从其他角落开始无法保证单向剪枝。

三、完整代码

classSolution{public:boolsearchMatrix(vector<vector<int>>&matrix,inttarget){intm=matrix.size();intn=matrix[0].size();intl=0;// 当前行，从 0 开始intb=n-1;// 当前列，从最后一列开始（右上角）while(l<m&&b>=0){if(matrix[l][b]==target){returntrue;}if(matrix[l][b]>target){b--;// 当前元素太大，目标在左边，列减一}elseif(matrix[l][b]<=target){l++;// 当前元素太小，目标在下边，行加一}}returnfalse;}};

四、算法流程图

4.1 整体搜索流程

输入：matrix, target [Step 1] 初始化起点 l = 0（从第一行开始） b = n - 1（从最后一列开始，即右上角） | v [Step 2] 进入主循环 | v l < m && b >= 0 ？ |否 v 【返回 false】 ← 循环结束，未找到 | |是 v [Step 3] 获取当前元素 current = matrix[l][b] | v current == target ？ |是 v 【返回 true】 ← 找到目标 | |否 v current > target ？ |是 |否 v v [Step 4] 列左移 [Step 5] 行下移 | | v v b-- l++ | | v v 回到 Step 2 回到 Step 2

4.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 = 5 初始：l=0, b=4 第一轮： matrix[0][4] = 15 > 5 → b-- → b=3 第二轮： matrix[0][3] = 11 > 5 → b-- → b=2 第三轮： matrix[0][2] = 7 > 5 → b-- → b=1 第四轮： matrix[0][1] = 4 < 5 → l++ → l=1 第五轮： matrix[1][1] = 5 == 5 → 返回 true 找到目标！共执行 5 步。

4.3 具体示例执行流程（未找到目标）

输入：target = 20 初始：l=0, b=4 第一轮：matrix[0][4] = 15 < 20 → l++ → l=1 第二轮：matrix[1][4] = 19 < 20 → l++ → l=2 第三轮：matrix[2][4] = 22 > 20 → b-- → b=3 第四轮：matrix[2][3] = 16 < 20 → l++ → l=3 第五轮：matrix[3][3] = 17 < 20 → l++ → l=4 第六轮：matrix[4][3] = 26 > 20 → b-- → b=2 第七轮：matrix[4][2] = 23 > 20 → b-- → b=1 第八轮：matrix[4][1] = 21 > 20 → b-- → b=0 第九轮：matrix[4][0] = 18 < 20 → l++ → l=5 第十轮：l=5 不满足 l < m，循环退出 返回 false（未找到）

4.4 为什么从右上角开始

以 4x4 矩阵为例： col=0 col=1 col=2 col=3 row=0 1 2 3 4 row=1 5 6 7 8 row=2 9 10 11 12 row=3 13 14 15 16 右上角 (l=0, b=3) = 4 特性： - 往左走（b--）：值变小（同行左边元素更小） - 往下走（l++）：值变大（同列下方元素更大） 这保证了每次比较后只能往一个方向走，不会丢失任何可能性。 如果从左上角开始 (l=0, b=0) = 1： - 往右走（b++）：值变大 - 往下走（l++）：值变大 两个方向都可能导致 target，无法剪枝。

五、逐行解析

5.1 初始化起点

intl=0;// 当前行intb=n-1;// 当前列（右上角）

选择右上角的原因：

• 同行左侧都是比它小的元素（往左走值变小）
• 同列下方都是比它大的元素（往下走值变大）
• 形成天然的搜索剪枝条件

5.2 主循环逻辑

while(l<m&&b>=0){if(matrix[l][b]==target){returntrue;}if(matrix[l][b]>target){b--;}elseif(matrix[l][b]<=target){l++;}}

三种情况：

5.3 循环结束条件

returnfalse;

何时返回 false：

• l >= m：已经越过最后一行（第 m 行不存在）
• b < 0：已经越过第一列（第 -1 列不存在）
• 两种情况都说明已经搜索完所有可能的路径

六、复杂度分析

最坏情况演示：

m=5, n=5 的矩阵，最多走 5+5-1=9 步： l 从 0 到 4（5 步） b 从 4 到 0（4 步）

七、面试追问

八、相关题目