240. 搜索二维矩阵 II
3 min
题目
解法：右上角搜索
思路
核心思想是从右上角开始搜索，根据当前值与目标值的大小关系决定移动方向。
正确性证明：矩阵行列递增的特性保证了搜索路径的单调性。当当前值大于目标值时，由于列递增，下方元素必然更大，因此向左移动排除整列；当小于目标值时，由于行递增，左侧元素必然更小，因此向下移动排除整行。这种移动方式确保不会错过任何可能的解。
- Step 1: 初始化位置为矩阵右上角(x=0, y=n-1)
- Step 2: 循环直到越界：比较matrix[x][y]与target
- Step 3: 相等则返回true；过大则左移(y—)；过小则下移(x++)
- Step 4: 循环结束未找到则返回false
复杂度
- 时间复杂度: ，最坏情况遍历所有行和列
- 空间复杂度: ，仅使用常数额外空间
代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) return false;
int m = matrix.size();
int n = matrix[0].size();
int x = 0;
int y = n - 1;
while (x < m && y >= 0) {
if (matrix[x][y] == target) {
return true;
} else if (matrix[x][y] > target) {
// 当前值比 target 大，说明这一列下方的数肯定也更大（列递增），只能往左找
y--;
} else {
// 当前值比 target 小，说明这一行左边的数肯定也更小（行递增），只能往下找
x++;
}
}
return false;
}
};