最近在刷二分搜索专题卡住我时间最久的一道题就是这个 Grapevine。判题页上给它的编号是 12192有些英文题库里对应着 4478题目内容完全一样。没看题解之前我一度以为要用什么诡异的迷宫搜索或者滑动窗口看懂之后才发现核心就是一层一层的二分先二分答案边长再在每一行里二分查找左边界。说实话这道题是典型的“代码短、思路长”非常适合用来理解二维有序矩阵上的单调性也适合想系统刷二分的人收藏。如果你现在刷到这道题大概率正在经历两个阶段一是完全没思路盯着矩阵发呆二是看了别人的写法觉得这也太简单了但真的自己动手写却会在 check 函数的边界上反复 WA。这篇我把这道题的完整推导、正确性证明、C 实现还有我在本地和 OJ 上踩过的坑全部写出来。虽然年代有点久远但这道题作为经典二分教学题的含金量一点没降。1. Grapevine 的题意里藏着哪些容易被忽略的条件1.1 矩阵的“二维不降序”到底意味着什么题目输入的是一个 n 行 m 列的整数矩阵有一句关键描述每一行从左到右是不降的每一列从上到下也是不降的。这句话是整个题目的支点比后面的查询规则重要得多但很多人读题的时候就扫过去了。用大白话解释矩阵里任何一个位置它左边的数和上边的数一定不大于它它右边的数和下边的数一定不小于它。也就是说只要你站在某个格子上往右下方向走数值只会变大或持平往左上方向走数值只会变小或持平。这种结构在算法里叫二维偏序简称有序矩阵。这个性质最直接的应用是如果你取出一个矩形区域比如从第 i 行到第 ik-1 行、第 j 列到第 jk-1 列那么这个区域里的最小值一定是左上角那个格子 a[i][j]最大值一定是右下角那个格子 a[ik-1][jk-1]。因为从左上角到右下角沿着行和列方向都在变大中间所有格子都介于这两个值之间。这一点在后面判定正方形是否合法时会反复用到算是整个算法的地基。1.2 查询的本质是在找最大可行正方形题目会给很多次询问每次给两个整数 L 和 U要求你在矩阵里找一个正方形正方形的每条边都平行于矩阵的边且正方形内所有格子的数值都落在 [L, U] 这个闭区间里。输出这个正方形最大的边长如果连一个格子都满足不了就输出 0。注意两个常见的理解偏差。第一正方形必须是轴对齐的不能旋转也不能是斜着的。它等价于取连续的 s 行和连续的 s 列行和列的数量一样。第二题目问的不是“有多少个正方形”也不是“正方形内有多少个数在区间内”而是“满足条件时边长最大是多少”。所以答案是一个整数 s范围从 0 到 min(n, m)。我一开始还犯过另一个错误以为要统计矩阵里所有值在 [L, U] 之间的最大连通区域那就要上并查集或者 BFS 了。但题目限定了“正方形”问题瞬间变成了一个几何判定问题这让二分答案有了施展空间。1.3 判断一个正方形是否合法的关键引理结合刚才说的矩阵性质给定正方形左上角 (i, j) 和边长 s我们不需要遍历 s 的平方个格子去验证只需要看两个端点最小值检查a[i][j] L最大值检查a[i s - 1][j s - 1] U如果这两个都满足那么正方形内所有格子必然都在 [L, U] 内。这是由矩阵从上到下、从左到右都不降的性质直接推出的。这个引理非常强把 O(s²) 的验证压缩成了 O(1)。整个问题从“网格搜索”变成了“在左上角集合和边长集合上的二分查找”。后面所有优化的前提都是这个引理所以做题前先把这个式子写在自己草稿纸上思路会顺很多。2. 从暴力枚举到二分答案优化思路的完整推导2.1 暴力做法的复杂度瓶颈在哪最容易想到的暴力做法是对于一次查询枚举所有可能的左上角 (i, j)再枚举边长 s然后用引理 O(1) 判断。总复杂度是 O(n * m * min(n, m))一次查询在 500 × 500 的矩阵上大约是 1.25 亿次操作如果查询次数再大一点直接就 TLE 了。有人说我可以枚举了左上角之后边长 s 从大到小试找到一个可行就 break这样平均快一些。但最坏情况仍然不变而且这样写没法保证每次查询都能快速结束一旦答案很小还是要枚举很多边长。暴力写法也有一点价值它能帮你验证“引理 枚举”的模型是正确的。我当时是先写了一个暴力版小数据对拍确认逻辑没问题之后才开始想优化。如果你现在还没想通最优写法建议先在草稿纸上把暴力的三重循环写出来感受一下慢在哪再往下看。2.2 单调性分析为什么答案可以二分二分答案能够成立的前提是答案具有单调性。放在这道题里要证明的是如果边长为 s 的正方形可行那么任意边长小于 s 的正方形也可行。证明其实很直观。假设你找到了一个边长 s 的正方形左上角是 (i, j)合法条件是 a[i][j] L 且 a[is-1][js-1] U。现在取一个更小的边长 t仍然以 (i, j) 为左上角那么新正方形的左上角没变所以 a[i][j] L 仍然成立新正方形的右下角是 a[it-1][jt-1]它一定不大于原来的右下角 a[is-1][js-1]因为 t-1 更小位置更靠左上。既然原来的右下角已经 U新的右下角自然 U。所以更小的正方形必然合法。这个单调性意味着对于一个查询答案是“前一段都可行后一段都不可行”的阶梯形状因此可以用二分来找最后一个可行的边长。上界是 min(n, m)下界是 0。另外边界 0 是天然合法的因为边长 0 的空正方形不包含任何格子总是可行的。这样二分答案的初始区间就是 [0, min(n, m)]不会出现无解的情况。2.3 另一个维度的二分行内 lower_bound 定位左边界二分答案框架确定之后剩下的事情就是如何高效实现 check(s)是否存在一个左上角使得边长为 s 的正方形合法。如果直接枚举左上角的行 i 和列 jcheck 一次仍然是 O(n * m)那二分答案只是把边长枚举优化成了 log 级别整体还是太慢。这时候要借助每行有序的性质对列方向做一次二分。思考过程是这样的固定正方形顶部的行 i 后左上角的列 j 必须满足 a[i][j] L也就是 j 不能小于第一个值大于等于 L 的列。又因为正方形里最大的数是右下角 a[is-1][js-1]为了让这个值尽量小从而更有可能 U我们应该让左上角尽量靠左。所以对于第 i 行只需要找唯一值得尝试的位置第一个大于等于 L 的列也就是 lower_bound 的结果。这是一个很典型的贪心加单调性的组合列 j 向右移动时最小值 a[i][j] 变大同时右下角 a[is-1][js-1] 也变大所以“最左边能满足最小值约束的位置”就是“最大值最小”的位置。如果连这个位置都放不下边长 s 的正方形那么同一行更靠右的位置更不可能放下。3. 核心算法框架二分边长 行内二分check 函数的正确性与复杂度3.1 check 函数的设计逻辑完整的算法流程如下。第一步对当前查询的 L 和 U二分答案边长 s区间是 [0, min(n, m)]。第二步写一个 check(s) 函数判断是否存在某个边长为 s 的正方形完全落在 [L, U] 内。第三步在 check 里枚举正方形顶部的行 i从 0 到 n-s因为如果顶行超过 n-s底部行 is-1 就越界了。对于每个 i在当前行中用 lower_bound 找到第一个 L 的列 left然后判断两件事left s - 1 m也就是以 left 为起点放得下边长为 s 的正方形a[i s - 1][left s - 1] U也就是右下角没有越出区间上限。如果这两条都满足return true。所有行都试完都不行return false。这个 check 函数里最反直觉的一点是它没有显式检查 a[i][left] L。其实不需要因为 left 是 lower_bound 的结果天然满足这个条件。它也没有检查 a[i][left] U因为这项检查被右下角的检查覆盖了如果左上角 U由于矩阵递增右下角一定也 U一定会被挡下来。可以写一个伪代码帮助理解bool check(int s, int L, int U) { for (int i 0; i s - 1 n; i) { int left lower_bound(a[i].begin(), a[i].end(), L) - a[i].begin(); if (left s - 1 m) continue; if (a[i s - 1][left s - 1] U) return true; } return false; }先判断放不放得下再判断数值是否超上限顺序不能反否则可能用越界的列下标去访问 a[is-1][lefts-1]本地不报错但下标越界OJ 上就是随机 WA 或者 RE。3.2 单调性证明与边界情况二分答案的单调性在前面已经证明过这里再补一个反方向的直觉如果某个边长 s 不可行那么更大的边长也一定不可行吗其实不一定因为可能出现一个更大的正方形它的左上角位置不同恰好整体值都更靠右反而落在区间内。但这不影响我们二分因为二分答案只需要“可行集合是前缀”不要求“不可行集合是后缀”的证明方向反过来成立。这里有个容易混淆的点二分答案要求的是“若 s 可行则所有小于 s 都可参考”还是“若 s 可行则大于 s 不可行”答案是前者。也就是说我们找的是最大的可行边长可行集合是一个从 0 开始的连续前缀二分时用标准的右边界收缩写法int lo 0, hi min(n, m); while (lo hi) { int mid (lo hi 1) / 2; if (check(mid, L, U)) lo mid; else hi mid - 1; } cout lo \n;为什么 mid 要写成 (lo hi 1) / 2也就是向上取整因为当 check(mid) 返回 true 时mid 可能是正确答案lo 不能移到 mid1否则会跳过答案返回 false 时mid 一定不是答案hi 可以移到 mid-1。这是二分答案的经典写法配合 mid 向上取整可以避免 lo 和 hi 相邻时死循环。边界情况主要集中在三个方面。一是 left m说明当前整行都小于 L这一行作为正方形顶行肯定不行但要继续枚举下一行因为下一行数值更大可能突然就有满足 L 的元素了。二是 left s - 1 m说明即使这一行存在大于等于 L 的列但从这个列开始往右凑不齐 s 列。三是整个矩阵都没有格子落在 [L, U] 内此时 check(1) 都是 false二分结束 lo 保持 0输出 0符合题意。3.3 整体时间复杂度估算一次查询的复杂度分成两层外层二分答案需要 O(log(min(n, m))) 次 check每次 check 最多枚举 n - s 1 行对每行做一次 lower_bound也就是 O(log m)。总复杂度是 O(n * log m * log(min(n, m)))。如果 n 和 m 都是 500这个值大约是多少呢500 乘以 9 乘以 9 约等于四万次基本操作一次查询四万次级别即使 Q 有几万整体也能在合理时间内跑完。实际测试中这个算法在有 O2 优化的编译环境下表现很稳。我还见过另一种写法在 check 里对每一行同时用 lower_bound 找 L 和 upper_bound 找 U然后判断两个位置之间的列数是否 s。这个写法也能过但多了一次二分而且还需要额外判断 U 那边的边界代码更啰嗦。核心原因是我们真正需要的只是“最小的合法左上角列”并不需要知道当前行有多少列的值在区间内因为正方形是向右下延伸的右下角是否超上限要看了下一行那个元素才能真正确定。4. 可直接提交的 C 实现与关键代码注释4.1 完整代码下面是一份可以直接提交的 C 代码为了适应不同的编译环境我用了 vector 存储矩阵。注释里的关键点都是我在本地对拍时确认过的。#include bits/stdc.h using namespace std; int n, m; vectorvectorint a; bool check(int s, int L, int U) { for (int i 0; i s - 1 n; i) { int left lower_bound(a[i].begin(), a[i].end(), L) - a[i].begin(); // 当前行第一个 L 的位置放不下 s 列直接跳过 if (left s - 1 m) continue; // 正方形右下角的值不能超过 U if (a[i s - 1][left s - 1] U) return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int kase 1; while (cin n m (n || m)) { a.assign(n, vectorint(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } int Q; cin Q; // 注意不同题库对输出 Case 标签的要求不一样提交前看题目描述 cout Case kase :\n; while (Q--) { int L, U; cin L U; int lo 0, hi min(n, m); while (lo hi) { int mid (lo hi 1) / 2; if (check(mid, L, U)) lo mid; else hi mid - 1; } cout lo \n; } } return 0; }代码很短短到第一次过样例的人都会怀疑就这么点东西但就是这几十行已经把二维有序矩阵、贪心、二分答案三个知识点压在一起了。4.2 lower_bound 和 upper_bound 的选择一个必须说清的细节很多人在 check 里会犹豫到底该用 lower_bound 还是 upper_bound要不要两个都用。我的结论是只需要一次 lower_bound。原因很简单设 left 是当前行第一个 L 的列。如果以 (i, left) 为左上角、边长为 s 的正方形合法那么就找到了答案如果它不合法即 a[is-1][lefts-1] U那么把 left 右移右下角 a[is-1][lefts-1] 只会更大更不可能 U。所以同一行的其他列都不用试。那 upper_bound 在什么时候会有用如果题目要求的不是正方形而是随便一个矩形或者要求统计区间内的个数那么 upper_bound 就有用了。但这里判断的是从左上角延伸的正方形当前行只贡献了左上角的列号右下角其实在更下面一行所以只凭当前行无法确定右边界。用 upper_bound 算出来的当前行区间对判断右下角没有任何帮助。这是我踩过的一个直觉陷阱写出来希望大家少走弯路。还有一个细节lower_bound 如果返回的是 end()说明整行都小于 L。left 变成了 mleft s - 1 m直接 continue不会访问越界。如果 L 比整行都小left 是 0就是这一行最左边的列也是符合贪心直觉的。4.3 输入输出与多组数据处理的注意事项这道题是多组数据读入 n 和 m当 n 和 m 同时为 0 时结束所有数据。所以主循环要写成 while (cin n m (n || m))注意这里不能用 n m 来判断因为如果 n 是 500、m 是 -500相加是 0但矩阵维度不可能是负数所以实际题目中 n 和 m 非负用 n || m 更严谨。另外cin 和 cout 在做了 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 之后性能通常够用但如果你的编译器版本比较老或者题库不认这两个优化换成 scanf 和 printf 也可以。核心算法复杂度不高输入输出反而是本题最容易出问题的地方之一。还有输出格式的坑有的题库要求每组数据前输出 “Case 1:”有的要求每组数据内部每行答案前加前缀甚至有的直接不要求任何标签。最稳妥的做法是读一遍题目输出描述不要只看样例格式。我的代码里是按带 Case 标签的格式写的如果你在别的题库遇到格式问题改这一行就行。5. 调试实录我在本地和 OJ 上踩过的坑5.1 二分上界取 min(n, m) 而不是 max第一次写的时候我很顺手地把二分上界写成了 max(n, m)。因为数学直觉告诉我正方形的边长不能超过行数也不能超过列数所以应该取其中较大的不应该取较小的那个。这个错误当时在本地小样例上完全没暴露因为小数据里 n 和 m 差别不大最大合法答案不可能超过较小的维度。直到对拍时遇到 2 行 10 列的矩阵check(5) 会尝试枚举顶部行底部行 i4 可能越界虽然 check 里限制了 i 的范围但二分上界写大了会让 check 在明显不可能的长度上反复试探虽然结果可能碰巧正确但会让整个程序的思维模型变得混乱。改成 hi min(n, m) 之后二分区间才是真正合理的答案范围。排查这个问题的思路很简单把每次 check 的 mid 打印出来看它是否超过了 min(n, m)。如果你发现检查了大于 min(n, m) 的边长检查代码里所有跟边长有关的行号列号多半就会发现问题。5.2 check 里漏掉“放不下”导致的越界这是我 AC 之前卡得最久的一个 bug。我当时写的判断是 if (left s m) continue觉得 left 是下标下标加边长超过 m 就是不合法。但忽略了 left 是 0 基下标正方形占用的最后一列下标是 left s - 1合法的条件是 left s - 1 m也就是 left s m。我那个写法把 left s m 的合法情况也 continue 掉了。举个例子m 5left 2s 3这个正方形占用第 2、3、4 列下标 2 3 - 1 4 5是合法的。但按照 left s m 的判断2 3 5 为假判断不出来如果反着写错比如写成 left s m就会漏掉 left 1, s 4 的边界。这类边界问题用对拍最容易发现构造一组列号用满的数据比如 m 3、left 0、s 3马上就能暴露。另外如果 left s - 1 m 成立就 continue这个行为本身也是正确的因为当前行的 left 已经是最靠左的合法列它都放不下 s 列更靠右的列更放不下不需要继续在这行里找了。5.3 TLE 之后的思考什么时候该换用 O(n m) 的扫描二分答案嵌套二分查找的写法在 n 和 m 都在 500 左右的经典数据下非常轻松但如果你在数据范围更大的题库里交同一份代码可能会 TLE。这时候要想到用扫描代替二分的套路。具体来说对于一次查询固定 L 之后每一行第一个 L 的列 left[i] 其实有着单调性因为矩阵是列间不降的上一行在 left 这个位置的值大于等于 L那么下一行同样位置的值也一定大于等于 L所以下一行的 left 不会比上一行更大。这意味着可以用一个指针从最右边开始一边向下移动行一边向左调整列指针每一行 O(1) 地得到 left。这样 check(s) 的复杂度能从 O(n log m) 降到 O(n)整个查询从 O(n log m log) 降到 O(n log) 甚至更优。但这属于进阶优化适合数据范围很大的变种题。对原题而言二分写法已经足够清晰我反而建议新手先吃透二分版再去看扫描版因为扫描版的指针移动逻辑需要更强的直觉才能写对。5.4 对拍时发现答案总是差一的小教训还有一次我发现答案总是比期望值小 1排查了很久最后发现是二分写成了 mid 向下取整。当 check(mid) 返回 true 时我把 lo 更新成 mid 1这就是经典错误mid 本身可能已经是最后一个可行解加 1 之后跳过了它。正确的是 lo mid配合 mid 向上取整。换句话说要找“最大的可行答案”一定要保证可行答案不会在更新过程中被丢掉。这类问题的排查经验是构造一个答案刚好等于上界的数据比如 n 3、m 3查询 L 和 U 覆盖整个矩阵正确答案应该是 3。如果程序输出 2十有八九是二分边界处理出了问题而不是 check 函数的问题。先修二分再怀疑 check定位会快很多。6. 同类题目怎么串起来从一维二分到二维二分的学习路线6.1 二维单调矩阵上的常见套路有序矩阵这个条件在算法题里反复出现。常见方向有三个一是在每一行做二分比如搜索目标值是否存在二是按某种对角线或 Z 字形走法扫描比如从右上角开始找目标三是利用答案的单调性做二分答案本题就是这一类。这三种套路的关键区别在于题目问的是“是否存在某值”还是“求最优值”。如果只是存在性判断用双指针扫描往往最简单如果是求满足条件的最值而且可行解集合有单调性二分答案就是首选。Grapevine 正好落在第三种而且比一般的二分答案多了一步“行内二分”是两个二分套在一起所以它特别适合作为从一维二分过渡到二维二分的训练题。学的时候可以做一个横向对比在一维有序数组中找满足条件的区间常用 lower_bound 和 upper_bound 组合在二维有序矩阵中找满足条件的正方形就要把“行的有序性”和“答案的单调性”结合起来。核心都是在有序空间上做排除法。6.2 如何练习从“会写代码”到“能讲清楚证明”我的建议是不要急着看题解代码先自己把三件事写下来为什么答案可以二分为什么 check 里只看每行的第一个合法列就够了为什么右下角的值可以代表整个正方形的最大值。这三句话写清楚了代码只是顺水推舟。如果还想加深理解可以尝试换一种 check 写法不二分边长而是枚举左上角然后对每条可行行直接二分最大边长最后取所有行的最大值。这个写法和二分答案在时间复杂度上差不多但能帮你确认对“行内 lower_bound 定位左边界”这件事的掌握程度。两种写法本地对拍结果应该完全一致。我个人的体会是这种二维有序矩阵的题目真正容易出错的从来不是二分模板而是边界条件下标和“最左合法列”的贪心直觉。把 3 × 3 的小矩阵画在草稿纸上随手标出 L 和 U手动走一遍 check比看十篇题解都有用。以后遇到再复杂的棋盘或矩阵类题目这个画格子推不等式的习惯帮我省了大量调试时间。