跳到主要内容

LeetCode 240. 搜索二维矩阵 II

本节目标

从右上角开始阶梯搜索，每次按大小关系排除一整行或一整列。

这道题是矩阵解题框架中的有序排除母题。二维有序并不意味着必须对每行独立二分；选对起点后，每次比较都能排除一整行或一整列。

查看原题

题意与约束​

给定一个矩阵，每行从左到右递增，每列从上到下递增。判断目标值 target 是否存在。

第一反应：逐行查找​

逐个扫描需要 O(mn)；对每行二分可以做到 O(m log n)。这些方法都只利用了行有序，没有同时利用列方向的单调性。

为什么从右上角开始​

右上角元素同时具有两种可用关系：

  • 它是当前行剩余部分的最大值；
  • 它是当前列剩余部分的最小值。

若当前值大于目标，当前列下方只会更大，因此整列可以排除，向左移动。若当前值小于目标，当前行左侧只会更小，因此整行可以排除，向下移动。

循环不变量是：若目标存在，它一定仍在以当前位置为右上角的候选子矩阵中。每步至少删除一行或一列，搜索不会回头。

代码实现​

实现先处理空矩阵，再从右上角沿“向左或向下”的阶梯路径搜索。

C++17
#include <vector>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) {
            return false;
        }

        int row = 0;
        int col = static_cast<int>(matrix[0].size()) - 1;
        while (row < static_cast<int>(matrix.size()) && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            }
            if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }
};

复杂度分析​

  • 时间复杂度：O(m + n)，最多向下移动 m 次、向左移动 n 次。
  • 空间复杂度：O(1)。

易错点​

  • 从左上角开始，当前值与目标的大小关系无法唯一决定移动方向。
  • 当前值较大时向下移动，进入更大的区域。
  • 只利用行有序，遗漏列有序带来的整列排除。
  • 空矩阵时直接读取第一行。

模式迁移​

只要二维结构允许从某个角落出发，并根据一次比较安全排除整行或整列，就可以尝试阶梯搜索。关键不是矩阵外形，而是该角落在两个方向上分别承担最大值和最小值边界。