LeetCode 1139. 最大的以 1 为边界的正方形

2021-09-13 HGNULB 约 12 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1139. 最大的以 1 为边界的正方形

题意分析

题目要在 0/1 网格里找一个正方形子矩阵，要求它的四条边上的格子全是 1，内部是什么完全不限制，返回这个正方形的面积（不是边长）。「只约束边界、不约束内部」是本题与经典最大全 1 正方形最本质的差别，也意味着任何基于「整块都是 1」的状态定义都会漏掉合法答案。

判定一个候选正方形是否合法，需要同时验证四条边：上边一整行连续 1、下边一整行连续 1、左边一整列连续 1、右边一整列连续 1。这四条件都是「某个方向上连续 1 的长度够不够」的形式，提示我们应当预先把每个格子在各方向上的连续 1 长度算好，让单次验证降到常数时间。

约束里网格的行数和列数都不超过 100，格子总数一万级别，这个规模明确允许在枚举每个位置之后再花一个正比于边长的循环去试探边长，也就是说三层循环量级的做法是被接受的，不必强求更优。反过来说，如果不做任何预处理直接按定义验证四条边，验证本身又要一层循环，整体会多出一个数量级。

边界要单独想：网格里一个 1 都没有时答案是 0，不能返回 1；单个孤立的 1 本身就是边长为 1 的合法正方形，面积是 1；返回值是边长的平方而不是边长，最后一步千万别漏。

解法：方向连续 1 动态规划

核心思路

暴力做法是枚举正方形的左上角和边长，然后沿四条边逐格检查是否为 1，枚举是 $O(mn \cdot \min(m,n))$ 种候选，每次检查又要 $O(\min(m,n))$ 步，总量级来到四次方。瓶颈非常清楚：同一段格子会被无数个候选正方形反复扫描，比如某一行上的连续 1，几乎每个包含它的候选都要重新数一遍。

观察到「一条边合法」等价于「从边的某个端点出发，沿该方向连续 1 的个数不小于边长」，而「从某格出发向左连续多少个 1」「向上连续多少个 1」这两个量本身满足非常简单的递推，可以在一次遍历里全部算出来。于是把重复扫描换成一次预处理，之后每条边的验证都变成一次数组读取加一次比较。

状态定义写清楚：leftOnes[row][col] 表示以 (row, col) 为右端点、向左延伸的最长连续 1 的长度（该格为 0 时取 0）；upOnes[row][col] 表示以 (row, col) 为下端点、向上延伸的最长连续 1 的长度。转移是 leftOnes[row][col] = leftOnes[row][col-1] + 1，upOnes[row][col] = upOnes[row-1][col] + 1，均在该格为 1 时才成立，为 0 时直接保持 0。

有了这两张表，就以 (row, col) 作为正方形的右下角来枚举。此时下边和右边分别由 leftOnes[row][col] 和 upOnes[row][col] 直接给出上界，所以候选边长最大只能是二者的较小值。再从这个上界往下试探边长 size，算出左上角坐标 (row - size + 1, col - size + 1)，只需再验证两件事：左边那一列从左下角向上够不够 size 个 1，即 upOnes[row][leftCol] ≥ size；上边那一行从右上角向左够不够 size 个 1，即 leftOnes[topRow][col] ≥ size。四条边至此全部覆盖。

试探时从大到小递减并在成功时立刻 break，同时把循环下界卡在当前最优 best 上——比 best 小的边长即使合法也不会改进答案，直接不试。这个剪枝让实际运行远快于最坏情况。

解题步骤

第一步，开两张与网格同尺寸的整型表 leftOnes 和 upOnes，一次双层遍历同时填好。遇到值为 0 的格子直接 continue，让它保持初始值 0，这是关键的一步：0 会像一堵墙一样切断连续段，后续所有跨过它的候选都会因为读到 0 而被自然否决，不需要任何额外的断点记录。

第二步，对值为 1 的格子先赋 1 再看能否接上前一格。写成「先置 1，再在 col > 0 时改成左邻加一」而不是直接写 leftOnes[row][col-1] + 1，是为了让第一列和第一行不必单独写特判，逻辑只有一处。

第三步，第二轮双层遍历枚举右下角。之所以选右下角而不是左上角，是因为 leftOnes 和 upOnes 天然是「向左」「向上」的，右下角能一次性读到下边和右边两条边的长度，坐标推导最短；若枚举左上角，就得再多维护向右和向下两张表。

第四步，取 maxSize = min(leftOnes[row][col], upOnes[row][col]) 作为该右下角的边长上界，然后 size 从 maxSize 递减到 best + 1。这里 size 的取值范围保证了 row - size + 1 和 col - size + 1 都不会为负，因为 upOnes 不会超过 row + 1、leftOnes 不会超过 col + 1，所以循环体内不需要任何越界检查。

第五步，验证左边和上边。命中就把 best 更新为 size 并 break，因为是从大到小试的，第一个命中的就是这个右下角能给出的最大边长，继续试只会更小。全部枚举结束后返回 best * best。

以 grid = [[1,1,1],[1,0,1],[1,1,1]] 走一遍：预处理后 leftOnes 三行分别是 [1,2,3]、[1,0,1]、[1,2,3]，upOnes 三行分别是 [1,1,1]、[2,0,2]、[3,1,3]。枚举右下角时，(0,0) 的 maxSize 是 1，size = 1 大于 best = 0，左上角就是自己，upOnes[0][0] = 1 ≥ 1 与 leftOnes[0][0] = 1 ≥ 1 均满足，best 更新为 1。接下来 (0,1) 到 (2,1) 这些位置的 maxSize 都不超过 1，循环条件 size > best 不成立直接跳过，中心的 (1,1) 因为是 0 连 maxSize 都是 0。最后来到 (2,2)：leftOnes 是 3、upOnes 是 3，maxSize = 3，size = 3 大于 best = 1，左上角是 (0,0)，检查左边 upOnes[2][0] = 3 ≥ 3 成立，检查上边 leftOnes[0][2] = 3 ≥ 3 成立，best 更新为 3。返回 3 * 3 = 9——整个 3×3 网格的外圈全是 1，中心的 0 完全不影响，这正体现了本题只看边界的特点。

代码实现

class Solution {
    // 预处理每个格子向左、向上连续 1 的数量后，可以 O(1) 检查某个候选正方形的四条边。
    public int largest1BorderedSquare(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] leftOnes = new int[rows][cols];
        int[][] upOnes = new int[rows][cols];

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == 0) {
                    continue;
                }

                leftOnes[row][col] = 1;
                if (col > 0) {
                    leftOnes[row][col] = leftOnes[row][col - 1] + 1;
                }
                upOnes[row][col] = 1;
                if (row > 0) {
                    upOnes[row][col] = upOnes[row - 1][col] + 1;
                }
            }
        }

        int best = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                int maxSize = Math.min(leftOnes[row][col], upOnes[row][col]);
                for (int size = maxSize; size > best; size--) {
                    int topRow = row - size + 1;
                    int leftCol = col - size + 1;
                    if (upOnes[row][leftCol] >= size && leftOnes[topRow][col] >= size) {
                        best = size;
                        break;
                    }
                }
            }
        }

        return best * best;
    }
}

func largest1BorderedSquare(grid [][]int) int {
    // 预处理每个格子向左、向上连续 1 的数量后，可以 O(1) 检查某个候选正方形的四条边。
    rows := len(grid)
    cols := len(grid[0])
    leftOnes := make([][]int, rows)
    upOnes := make([][]int, rows)
    for row := 0; row < rows; row++ {
        leftOnes[row] = make([]int, cols)
        upOnes[row] = make([]int, cols)
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] == 0 {
                continue
            }

            leftOnes[row][col] = 1
            upOnes[row][col] = 1
            if col > 0 {
                leftOnes[row][col] = leftOnes[row][col-1] + 1
            }
            if row > 0 {
                upOnes[row][col] = upOnes[row-1][col] + 1
            }
        }
    }

    best := 0
    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            maxSize := leftOnes[row][col]
            if upOnes[row][col] < maxSize {
                maxSize = upOnes[row][col]
            }
            for size := maxSize; size > best; size-- {
                topRow := row - size + 1
                leftCol := col - size + 1
                if upOnes[row][leftCol] >= size && leftOnes[topRow][col] >= size {
                    best = size
                    break
                }
            }
        }
    }

    return best * best
}

复杂度分析

时间复杂度：$O(m \cdot n \cdot \min(m, n))$，其中 m 和 n 分别表示网格的行数和列数。预处理是 $O(mn)$，枚举右下角是 $O(mn)$ 个位置，每个位置最多试探 $\min(m, n)$ 种边长且每次试探是常数时间；size > best 的下界剪枝使实际试探次数远小于上界。

空间复杂度：$O(mn)$，两张与网格同尺寸的辅助表分别存放每个格子向左和向上的连续 1 数量，枚举阶段只用了常数个额外变量。

关键点总结

「边界全 1」和「整块全 1」是两类完全不同的问题，前者不能套后者的 $dp[i][j] = \min(\text{三邻居}) + 1$。识别出约束只作用在边界上，是本题的第一个分水岭。

把「某方向连续 1 的长度」预处理成表，是矩阵类题目的通用加速手段。它把「验证一条边」从线性降到常数，代价只是 $O(mn)$ 的空间，这个交换在网格题里几乎总是划算的。

枚举方向要和预处理方向对齐。这里维护的是向左和向上，所以枚举右下角；若维护向右和向下就该枚举左上角。方向不匹配会逼你多维护两张表，白白增加出错面。

从大到小试探边长并把下界卡在当前最优上，是一个可迁移的剪枝模板：当目标是求最大值、且候选按大小有序可枚举时，凡是不可能超过已有最优的候选都不必验证。

面试视角上，面试官最想听到的是你如何从四次方的朴素验证一步步压到三次方，以及你怎么用两张表就覆盖了四条边——说清楚「下边和右边由右下角直接给出，左边和上边各需一次查表」这句话，基本就说明你真正想明白了。

返回的是面积不是边长。这类「问的量和维护的量差一层变换」的题，把最终返回值单独拎出来核对一遍是低成本高收益的习惯。

易错点总结

错误写法：直接套用最大全 1 正方形的 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 → 对用例 [[1,1,1],[1,0,1],[1,1,1]]，中心的 0 会把状态压到 1，返回 1，而正确答案是 9。

错误写法：返回 best 而不是 best * best → 对同一用例返回 3 而不是 9，题目问的是面积。

错误写法：预处理时对值为 0 的格子也执行 leftOnes[row][col] = leftOnes[row][col-1] + 1 → 连续段被 0 打断的信息丢失，对用例 [[1,0,1],[1,1,1],[1,1,1]] 会把第一行当成连续三个 1，错误地认为存在边长为 3 的正方形。

错误写法：只检查左边和上边，忘了下边和右边也要够长 → 若把 maxSize 直接写成 min(row, col) + 1 而不是取两张表的最小值，对用例 [[1,1,1],[1,1,0],[1,1,1]] 会把右下角为 (2,2) 的 3×3 当成合法，而它的右边一列存在 0，正确答案是 4。

错误写法：内层循环写成 for size = maxSize; size >= 1; size-- 并在命中时用 best = Math.max(best, size) 但不 break → 结果虽然仍对，但每个位置都要跑满 min(m,n) 次，对 100×100 全 1 网格的耗时是带剪枝版本的数十倍。

错误写法：内层循环写成从小到大 for size = 1; size <= maxSize; size++ 且命中就 break → 对用例 [[1,1],[1,1]]，size = 1 就命中并跳出，best 停在 1，返回 1 而不是 4。

错误写法：左上角坐标算成 row - size 和 col - size 漏掉加一 → 对用例 [[1,1],[1,1]] 枚举到 (1,1) 且 size = 2 时得到 topRow = -1，数组下标为负直接抛越界异常。

错误写法：验证左边写成 upOnes[topRow][leftCol] >= size → 读的是左上角向上的长度而非左下角向上的长度，左边这一列中间的 0 被跳过。对用例 [[1,0,0],[1,0,0],[1,1,1],[0,0,1],[1,1,1]]，右下角 (4,2) 处 size = 3 会因为 upOnes[2][0] = 3 而被误判成合法，返回 9，而正确答案是 1。

错误写法：验证上边写成 leftOnes[topRow][leftCol] >= size → 读成了左上角向左的长度，而左上角往左本来就没有那么多格。对用例 [[1,1],[1,1]]，(1,1) 处 size = 2 时读到 leftOnes[0][0] = 1 小于 2，完全合法的 2×2 被误杀，返回 1 而不是 4。

错误写法：maxSize 取 Math.max(leftOnes[row][col], upOnes[row][col]) → 下边和右边中较短的那条根本没被约束住。对用例 [[1,1,1],[1,0,1],[1,0,1]]，(2,2) 处会拿 3 去试探并通过，返回 9，而这三行的下边 [1,0,1] 并非全 1，正确答案是 1。

错误写法：Go 里只 make([][]int, rows) 而忘记为每一行 make([]int, cols) → 每行都是 nil 切片，第一次写入就 panic，任何非空用例都会崩。

相似题目

题目	难度	考察点
221. 最大正方形	中等	要求整块全 1，状态取三个邻居的最小值加一
1277. 统计全为 1 的正方形子矩阵	中等	同一状态定义，但把最大值改成对所有状态求和
85. 最大矩形	困难	长宽不必相等，逐行转成柱状图后用单调栈
84. 柱状图中最大的矩形	困难	一维版本，核心是找每根柱子左右第一个更矮的位置
1504. 统计全 1 子矩形	中等	计数而非求最值，需要按行累计高度并用单调栈摊还
562. 矩阵中最长的连续1线段	中等	需要四个方向的连续 1 表，含两条对角线
1292. 元素和小于等于阈值的正方形的最大边长	中等	判定条件是区域和上界，改用二维前缀和且边长具备单调性
304. 二维区域和检索 - 矩阵不可变	中等	二维前缀和的裸模板，容斥公式是后续矩阵题的基础
1314. 矩阵区域和	中等	二维前缀和加边界裁剪，考察下标夹取
1074. 元素和为目标值的子矩阵数量	困难	压缩行区间后退化成一维前缀和加哈希计数
363. 矩形区域不超过 K 的最大数值和	困难	同样压缩行区间，但需要有序集合做前缀和的上界查询