搜索二维矩阵 II

这是一道围绕算法展开的高频练习。建议先掌握「右上角搜索」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

算法

题目分析

这道题表面上是在处理「搜索二维矩阵 II」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考算法这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：从右上角出发，当前值大了就往左，小了就往下，每一步都能排除一整行或一整列。

推荐代码

推荐解法：右上角搜索

时间复杂度： O(m+n)

空间复杂度： O(1)

核心思路：从右上角出发，当前值大了就往左，小了就往下，每一步都能排除一整行或一整列。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int row = 0;
        int col = cols - 1;

        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            }
            if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }

        return false;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会从右上角开始搜索，利用行列的双单调性剪枝。

核心过程

右上角左边都更小，下边都更大。
如果当前值比目标大，就整列左移。
如果当前值比目标小，就整行下移。
直到找到目标或越界结束。

复杂度总结

时间复杂度 O(m+n)，空间复杂度 O(1)。

面试补一句：面试里要重点说明为什么每一步都能排除整行或整列。

核心思路

矩阵每行递增、每列递增，所以右上角是一个非常特殊的位置。它左边都更小，下边都更大，因此比较一次就能明确丢掉一整部分搜索空间。

步骤讲解

从右上角开始

初始位置设在第一行最后一列。

为什么这样做：这里只有两个明确方向：左边更小，下边更大。

对应代码提示：int row = 0, col = cols - 1;

根据比较结果移动

如果当前值大于目标就左移，小于目标就下移，等于则直接返回。

为什么这样做：每一步都能安全排除一整列或一整行。

对应代码提示：if (matrix[row][col] > target) col--; else row++;

易错点

从左上角开始不知道怎么走

左上角右边和下边都更大，比较后无法唯一决定移动方向。

正确理解：选右上角或左下角这种单调方向明确的起点。

把它当成普通二维二分

二维矩阵不是按整块全局有序，直接二分会失效。

正确理解：利用行列双单调性质做线性剪枝。

复杂度与适用判断

时间复杂度：O(m+n)

空间复杂度：O(1)

比其他方案更好在哪里：比逐行二分更直观，也更容易一次性利用两维单调性。

适用判断：矩阵同时满足行有序和列有序时，优先找一个比较后能唯一决定方向的角落。

额外提醒

右上角和左下角都是这种“比较一次就能决定方向”的黄金起点。