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

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
数组 动态规划 矩阵

题目描述

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

image-20260928230012634

题意分析

找出四条边全部为一的最大正方形，内部可以有零，返回它的面积；不存在这样的正方形时返回零。

一个候选由右下角和边长唯一确定。若每次重新扫描四条边，会反复检查相同的连续一，因此先记录每格向左、向上的连续一长度，再通过边界端点的记录判断整条边是否完整。

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

核心思路

[!blue]

leftOnes[row][col] 表示以当前格结尾、向左连续的一的个数，upOnes[row][col] 表示向上连续的一的个数，两者都包含当前格。当前格为零时均为零；为一时，分别在左邻格或上邻格的记录上加一，遇到矩阵边界就从一开始。按行扫描时，这些依赖都已经计算完成。

固定右下角 (row, col)，下边和右边要连续为一，所以候选边长最多为 min(leftOnes[row][col], upOnes[row][col])。对某个 size，左上角坐标是 topRow = row-size+1、leftCol = col-size+1；这个上界也保证两个坐标不会越界。

下边和右边已经由上界保证，剩下只需检查两条边：upOnes[row][leftCol] >= size 表示从左下角向上的左边完整，leftOnes[topRow][col] >= size 表示从右上角向左的上边完整。四条边都满足，候选就合法，内部无需检查。

best 保存目前找到的最大边长。每个右下角从最大候选边长递减尝试，首次成功就是这个角点的最大合法边长，可以停止；小于等于 best 的候选无法改善答案，也直接跳过。所有正方形都有唯一右下角，枚举全部角点就不会遗漏可能更大的答案，最后返回 best * best。

解题步骤

  • 计算两张方向长度表，零格保持零。
  • 枚举右下角，从两个方向长度的最小值开始尝试。
  • 查左下向上、右上向左是否都足够，命中更新。

代码实现

class Solution {
    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 {
    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(mn\min(m,n))$。预处理为 $O(mn)$；每个右下角最多尝试 $\min(m,n)$ 种边长，每次只查两项记录。
  • 空间复杂度：$O(mn)$，两张连续长度表。

关键点总结

[!green]

  • 两条边由候选上界保证，另外两条通过端点查表。
  • 固定角点时可行边长不一定单调，不能直接二分。

易错点总结

[!yellow]

  • 套用整块全一正方形状态，会错过内部含零的合法外框。
  • 只检查右下角两条边，会接受上边或左边缺口。
  • 直接返回最佳边长，遗漏题目要求的平方。
  • 某个边长失败后不能停止或据此二分，更小正方形的上边和左边已经换了位置，合法性不单调。
  • 全零时所有候选上界为零，答案保持零；任意单个一都能组成边长为一的合法正方形。

相似题目

题目 难度 关联与区别
221. 最大正方形 中等 原题整个正方形都必须为1，本题只要求四条边，可预处理向右、向下连续1长度。
750. 角矩形的数量 中等 原题只检查矩形四个角，本题必须确认整条边，不能只凭角点为1判定。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/42472779
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！