LeetCode 240. 搜索二维矩阵 II
目录
题目描述
题意分析
给定一个 $m \times n$ 的矩阵和一个目标值，判断目标值是否存在于矩阵中，返回布尔值即可，不要求返回位置。
有序性是题目给的最强信号：每行从左到右升序，每列从上到下升序。注意这两条只是「行内有序」加「列内有序」，矩阵整体按行拉平后并不是一个有序的一维数组——这正是它与 74. 搜索二维矩阵 的本质区别，74 额外保证每行首元素大于上一行末元素。
约束上 $m, n \le 300$，元素和目标值都在 $\pm 10^9$ 内，用
int即可，不存在溢出问题。边界情况：目标值比矩阵最小值（左上角）还小、比最大值（右下角）还大、矩阵只有一行或一列，算法都必须自然收敛到返回
false或正确命中。
解法：从右上角阶梯式搜索
核心思路
每行、每列分别递增，但矩阵按行展开后并不整体有序，所以不能像 74 题那样做一次普通二分。逐行二分是 $O(m\log n)$；更充分利用两个方向的有序性，可以从右上角开始，每次排除一整行或一整列。
右上角元素是当前行的最大值、当前列的最小值。若它大于
target，这一列当前位置以下只会更大，因此整列可以排除并左移；若它小于target，这一行当前位置左侧只会更小，因此整行可以排除并下移。循环不变量是：若目标存在，它一定在当前坐标左下方的剩余子矩阵中。每次比较都按有序性安全删除一行或一列，不变量持续成立；指针越界时剩余区域为空，因此目标不存在。左下角出发是完全对称的做法。
解题步骤
- 初始化
row = 0、col = n - 1，指向右上角。- 当
row < m && col >= 0时，将当前位置与target比较。- 相等直接返回
true；当前值过大就col--，排除当前列；当前值过小就row++，排除当前行。- 指针越界后返回
false。由于每轮只有一次左移或下移，最多执行m + n - 1次比较。- 例如样例中查找
5的路径为15 → 11 → 7 → 4 → 5，前三次左移，遇到 4 后下移并命中。
代码实现
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
int value = matrix[row][col];
if (value == target) {
return true;
}
if (value > target) {
col--;
} else {
row++;
}
}
return false;
}
}
func searchMatrix(matrix [][]int, target int) bool {
row := 0
col := len(matrix[0]) - 1
for row < len(matrix) && col >= 0 {
value := matrix[row][col]
if value == target {
return true
}
if value > target {
col--
} else {
row++
}
}
return false
}
复杂度分析
- 时间复杂度：$O(m+n)$。行下标最多增加 $m$ 次，列下标最多减少 $n$ 次。
- 空间复杂度：$O(1)$。
关键点总结
- 起点要选一个方向递增、另一个方向递减的角；右上角和左下角可行，左上角或右下角无法唯一决定排除方向。
- 比较不是只移动一步，而是在有序性的保证下排除当前剩余区域的一整行或一整列。
- 循环不变量同时解释了算法不会漏解，以及为什么越界时可以返回
false。- 面试若问逐行二分，复杂度为 $O(m\log n)$；阶梯搜索在一般长宽下上界更稳定，为 $O(m+n)$。
易错点总结
- 当前值大于目标时向下走：同列下方只会更大，应当左移。
- 从左上角出发：当前值偏小时，右移和下移都可能正确，无法排除一侧。
- 用
matrix.length - 1初始化列下标：非方阵时会漏列或越界，应使用matrix[0].length - 1。- 漏掉任一越界条件：目标大于所有元素时
row会到达m，目标小于所有元素时col会到达-1。- 把矩阵按行展开后整体二分：本题不保证下一行首元素大于上一行末元素。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 74. 搜索二维矩阵 | 中等 | 行间也有序，可展平成一维数组做一次全局二分 |
| 剑指 Offer 04. 二维数组中的查找 | 中等 | 本题原题，右上角排除法原样迁移 |
| 面试题 10.09. 排序矩阵查找 | 中等 | 同一模型换壳，可练习左下角出发的对称写法 |