LC240　搜索二维矩阵 II¶

中等通过率 57.5%python3核心代码模式矩阵样例通过牛客 AC数组二分查找分治矩阵

讲解章节：二分

一句话

从右上角出发，比目标大就左移一列、比目标小就下移一行。

解题思路¶

这题考什么¶

矩阵行内升序、列内升序，但整体拉直并不有序（第二行的开头可能小于第一行的末尾，样例里第 1 行末是 15、第 2 行头是 2），所以不能把它当成一个长度 m*n 的有序数组做一次二分。对每一行各做一次二分是 O(m log n)，正确但不是最优。

O(m + n) 的做法靠一个单调的角。挑右上角 (0, n-1) 当起点，它有个别处没有的性质：

它是所在**行**里最大的（行向右递增，它在最右）
它是所在**列**里最小的（列向下递增，它在最上）

于是每次比较都能整行或整列地排除：

matrix[r][c] > target  ->  这一整列（从当前行往下）都不小于它，
                           全都大于 target，第 c 列可以整列丢掉，c 减一
matrix[r][c] < target  ->  这一整行（从当前列往左）都不大于它，
                           全都小于 target，第 r 行可以整行丢掉，r 加一
相等                    ->  找到了

每一步要么减一列、要么加一行，走出矩阵之前最多走 (m - 1) + (n - 1) 步，所以是 O(m + n)。这条路径像沿着「值等于 target 的等高线」在阶梯上走，因此也叫阶梯搜索 / 二叉搜索树视角——把右上角看成根，向左是左子树（更小）、向下是右子树（更大），整个矩阵就是一棵二叉搜索树。与之相关的二分思路见二分。

左下角 (m-1, 0) 同样可用（列里最大、行里最小，向上变小、向右变大）。 左上角和右下角都不行：左上角向右与向下都变大，比目标小的时候两个方向都可能有解，排除不掉任何东西；右下角对称地也一样。

数据规模与复杂度¶

1 <= n, m <= 300，-1e9 <= matrix[i][j] <= 1e9，-1e9 <= target <= 1e9。时间 O(m + n)，最坏 600 步；空间 O(1)。逐格扫描是 O(m n) = 9e4，本题规模下其实也能过，但它没用上有序性；逐行二分是 O(m log n) 约 300 * 9 = 2700 步，也可行。阶梯搜索胜在代码短、常数小、没有二分的边界纠缠。

坑在哪¶

起点必须选右上角或左下角，不能选左上角。左上角处向右、向下都是变大，当 matrix[0][0] < target 时右边和下边都可能藏着答案，一步排除不了任何一侧，退化成需要回溯的搜索。右上角之所以可用，是因为它在两个可走方向上的单调性相反（向左变小、向下变大），比较结果能唯一决定该丢哪一片。
两个移动方向的下标增减不能写反：值偏大要往小的方向走，即列号减一；值偏小要往大的方向走，即行号加一。写反了会立刻走出矩阵，几乎总是返回 False。
循环条件是 r < m and c >= 0，两端各管一个方向：行号只增、上界是 m，列号只减、下界是 0。少写一半会在走到边上时下标越界。
相等要当场返回。若把等号并进某一个分支（例如写成 if v >= target: c -= 1），命中的那一格会被当成「偏大」而跳过，之后再也回不来，答案错成 False。
每次比较排除的是整行或整列的剩余部分，不是单个格子。理解这一点才知道为什么走过的路不用回头——被丢掉的那一列（从当前行往下的部分）里每个元素都不小于 matrix[r][c] > target，不可能藏着答案。
题面保证 m 与 n 至少为 1，不会遇到空矩阵；但退化成单行或单列时逻辑照样成立—— 单行时只会不断左移，等价于一次从右往左的线性扫描。
严格比对：返回的是布尔值，只有 true / false 两种，没有多解。

样例复核¶

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]]，m = n = 5。

target = 5，期望 true：

(0,4) = 15 > 5   丢掉第 4 列，c 变成 3
(0,3) = 11 > 5   丢掉第 3 列，c 变成 2
(0,2) = 7  > 5   丢掉第 2 列，c 变成 1
(0,1) = 4  < 5   丢掉第 0 行，r 变成 1
(1,1) = 5  == 5  命中，返回 true

target = 20，期望 false：

(0,4) = 15 < 20  r=1     (1,4) = 19 < 20  r=2
(2,4) = 22 > 20  c=3     (2,3) = 16 < 20  r=3
(3,3) = 17 < 20  r=4     (4,3) = 26 > 20  c=2
(4,2) = 23 > 20  c=1     (4,1) = 21 > 20  c=0
(4,0) = 18 < 20  r=5，越过下边界，循环结束，返回 false

两例都与期望一致；第二例走了 9 步，正好落在 m + n - 1 = 9 的上界上。

参考实现¶

solutions/leetcode/LC240/sol.py
from typing import List, Optional


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        # 从右上角出发：这一格是所在行的最大值、所在列的最小值，
        # 两个可走方向的单调性相反（向左变小、向下变大），
        # 所以一次比较就能唯一决定丢掉一整列还是一整行。
        # 左上角做不到这一点——向右向下都变大，比较结果排除不了任何一侧
        r = 0
        c = n - 1
        # 行号只增（上界 m）、列号只减（下界 0），两个条件各管一个方向，缺一会越界
        while r < m and c >= 0:
            v = matrix[r][c]
            # 相等必须当场返回。把等号并进下面某个分支会把命中的格子当成
            # 「偏大」或「偏小」跳过，之后再也走不回来
            if v == target:
                return True
            if v > target:
                # 当前值偏大：第 c 列从第 r 行往下的元素都不小于它，整段都大于 target，
                # 这一列可以整体丢掉。往小的方向走就是列号减一
                c -= 1
            else:
                # 当前值偏小：第 r 行从第 c 列往左的元素都不大于它，整段都小于 target，
                # 这一行可以整体丢掉。往大的方向走就是行号加一
                r += 1
        # 走出矩阵说明每一行每一列都已被合法地排除过，target 不存在
        return False

LC240 搜索二维矩阵 II¶