最近在刷二分搜索专题，卡住我时间最久的一道题就是这个 Grapevine。判题页上给它的编号是 12192，有些英文题库里对应着 4478，题目内容完全一样。没看题解之前，我一度以为要用什么诡异的迷宫搜索或者滑动窗口，看懂之后才发现，核心就是一层一层的二分：先二分答案边长，再在每一行里二分查找左边界。说实话，这道题是典型的“代码短、思路长”，非常适合用来理解二维有序矩阵上的单调性，也适合想系统刷二分的人收藏。
如果你现在刷到这道题，大概率正在经历两个阶段：一是完全没思路，盯着矩阵发呆；二是看了别人的写法，觉得这也太简单了，但真的自己动手写，却会在 check 函数的边界上反复 WA。这篇我把这道题的完整推导、正确性证明、C++ 实现，还有我在本地和 OJ 上踩过的坑全部写出来。虽然年代有点久远，但这道题作为经典二分教学题的含金量一点没降。
1. Grapevine 的题意里藏着哪些容易被忽略的条件
1.1 矩阵的“二维不降序”到底意味着什么
题目输入的是一个 n 行 m 列的整数矩阵，有一句关键描述：每一行从左到右是不降的，每一列从上到下也是不降的。这句话是整个题目的支点，比后面的查询规则重要得多，但很多人读题的时候就扫过去了。
用大白话解释：矩阵里任何一个位置，它左边的数和上边的数一定不大于它，它右边的数和下边的数一定不小于它。也就是说，只要你站在某个格子上，往右下方向走，数值只会变大或持平；往左上方向走，数值只会变小或持平。这种结构在算法里叫二维偏序，简称有序矩阵。
这个性质最直接的应用是：如果你取出一个矩形区域，比如从第 i 行到第 i+k-1 行、第 j 列到第 j+k-1 列，那么这个区域里的最小值一定是左上角那个格子 a[i][j]，最大值一定是右下角那个格子 a[i+k-1][j+k-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[i+s-1][j+s-1] <= U。现在取一个更小的边长 t，仍然以 (i, j) 为左上角，那么新正方形的左上角没变，所以 a[i][j] >= L 仍然成立；新正方形的右下角是 a[i+t-1][j+t-1]，它一定不大于原来的右下角 a[i+s-1][j+s-1]，因为 t-1 更小，位置更靠左上。既然原来的右下角已经 <= U，新的右下角自然 <= U。所以更小的正方形必然合法。
这个单调性意味着：对于一个查询，答案是“前一段都可行，后一段都不可行”的阶梯形状，因此可以用二分来找最后一个可行的边长。上界是 min(n, m)，下界是 0。
另外，边界 0 是天然合法的，因为边长 0 的空正方形不包含任何格子，总是可行的。这样二分答案的初始区间就是 [0, min(n, m)]，不会出现无解的情况。
2.3 另一个维度的二分：行内 lower_bound 定位左边界
二分答案框架确定之后，剩下的事情就是如何高效实现 check(s)：是否存在一个左上角，使得边长为 s 的正方形合法。
如果直接枚举左上角的行 i 和列 j，check 一次仍然是 O(n * m)，那二分答案只是把边长枚举优化成了 log 级别，整体还是太慢。这时候要借助每行有序的性质，对列方向做一次二分。
思考过程是这样的：固定正方形顶部的行 i 后，左上角的列 j 必须满足 a[i][j] >= L，也就是 j 不能小于第一个值大于等于 L 的列。又因为正方形里最大的数是右下角 a[i+s-1][j+s-1]，为了让这个值尽量小，从而更有可能 <= U，我们应该让左上角尽量靠左。所以对于第 i 行，只需要找唯一值得尝试的位置：第一个大于等于 L 的列，也就是 lower_bound 的结果。
这是一个很典型的贪心加单调性的组合：列 j 向右移动时，最小值 a[i][j] 变大，同时右下角 a[i+s-1][j+s-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，底部行 i+s-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[i+s-1][left+s-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 不能移到 mid+1，否则会跳过答案；返回 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; vector<vector<int>> 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, vector<int>(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[i+s-1][left+s-1] > U，那么把 left 右移，右下角 a[i+s-1][left+s-1] 只会更大，更不可能 <= U。所以同一行的其他列都不用试。
那 upper_bound 在什么时候会有用？如果题目要求的不是正方形，而是随便一个矩形，或者要求统计区间内的个数，那么 upper_bound 就有用了。但这里判断的是从左上角延伸的正方形，当前行只贡献了左上角的列号，右下角其实在更下面一行，所以只凭当前行无法确定右边界。用 upper_bound 算出来的当前行区间，对判断右下角没有任何帮助。这是我踩过的一个直觉陷阱，写出来希望大家少走弯路。
还有一个细节：lower_bound 如果返回的是 end()，说明整行都小于 L。left 变成了 m，left + 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) 会尝试枚举顶部行，底部行 i+4 可能越界，虽然 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 = 5，left = 2，s = 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，比看十篇题解都有用。以后遇到再复杂的棋盘或矩阵类题目，这个画格子推不等式的习惯帮我省了大量调试时间。
