最大的以 1 为边界的正方形 图解题解

以 1 为边界是什么意思，返回的是边长还是面积

给一张只装 0 和 1 的网格，找一个子正方形，要它四条边整圈全是 1，框里是 0 还是 1 不管。返回格子总数，边长 k 就返回 k 乘 k，不是 k。样例 grid = [[1,1,1],[1,0,1],[1,1,1]] 输出 9，中间那 0 落在框内、不碰边框。

边框全 1 逐格去数，一张 100×100 的网格要数多少遍

光候选正方形就有 O(n³)（大 O 记号，量级估计）个：每个左上角配上 1 到 min(m, n) 的一种边长。每个还得沿四条边逐格看全不全 1，约 4k 步再叠 O(n)，合起来近 O(n⁴)。相邻正方形的边大段重叠、同格反复重数。

把「这条边全是 1 吗」预先算成一个数，查边框就不再走格子

先给每格记两个数：向下、向右各连续几个 1，存进 down 和 right 两张表。两表用小递推（拿邻格结果推出当前格）自底向上、从右往左填（从最下一行、最右一列起倒推，算到当前格时下邻、右邻都已备好）：当前格 (i, j)（即（行号，列号），从 0 数起）是 1 时，down[i][j] 等于下邻 down 加 1、right[i][j] 等于右邻 right 加 1；是 0 就记 0，链子在此断。这就是动态规划（每格连续 1 的长度算好存表，查边框直接取）。

一条边到底看哪个角的哪张表，套错角会怎样

判断以 (i, j) 为左上角、边长 k 的正方形，四条边各查一个角、都 O(1)：上边看左上角 right[i][j]、左边看左上角 down[i][j]，下边看左下角 (i+k-1, j) 的 right、右边看右上角 (i, j+k-1) 的 down，四个都不小于 k 边框才全 1。最易套错的是把下边、右边也按左上角查，认错角就查了条不存在的边。

拿演示的 4×4 网格，把两张表填出来再枚举边长

演示网格 4×4，(0,0)、(3,3) 是 0，其余十四格全 1，同规则填两表。第 0 行的 right 从右往左：(0,3) 到头记 1，(0,2) 加 1 得 2，(0,1) 再加 1 得 3，(0,0) 遇 0 断成 0；第 1 列的 down 从下往上：(3,1) 记 1、(2,1) 得 2、(1,1) 得 3、(0,1) 得 4；第 2 行、第 3 列同理给出 (2,1) right=3、(0,3) down=3。枚举边长：4 的唯一起点 (0,0) 是 0 出局；缩到 3，别的左上角也这样查四角，这里演代表 (0,1)：上左下右依次读 right[0][1]=3、down[0][1]=4、right[2][1]=3、down[0][3]=3，都≥3 全过，返回 3 乘 3 等于 9。

下边误看成左上角的计数，一个本该 9 的答案为什么会缩水

填两表扫一遍网格 O(m·n)；枚举边长 min(m, n) 种、每种全网格 O(1) 查边，方阵约 O(n³)；两表占 O(m·n) 空间。返回值写成边长 k 而非面积 k 乘 k，样例 9 会缩成 3。起点角认错，答案就莫名偏小。以为框里也得全 1、把带 0 的 9 判掉——其实只看边框这圈。边界：中间 0 仍算 9，单行最多 1×1，全 0 返回 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        down = [[0] * n for _ in range(m)]
        right = [[0] * n for _ in range(m)]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if grid[i][j]:
                    down[i][j] = down[i + 1][j] + 1 if i + 1 < m else 1
                    right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1
        for k in range(min(m, n), 0, -1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if (
                        down[i][j] >= k
                        and right[i][j] >= k
                        and right[i + k - 1][j] >= k
                        and down[i][j + k - 1] >= k
                    ):
                        return k * k
        return 0

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int down[m][n];
        int right[m][n];
        memset(down, 0, sizeof down);
        memset(right, 0, sizeof right);
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
                    right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
                }
            }
        }
        for (int k = min(m, n); k > 0; --k) {
            for (int i = 0; i <= m - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
                        && down[i][j + k - 1] >= k) {
                        return k * k;
                    }
                }
            }
        }
        return 0;
    }
};

Java

import java.util.*;
class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] down = new int[m][n];
        int[][] right = new int[m][n];
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
                    right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
                }
            }
        }
        for (int k = Math.min(m, n); k > 0; --k) {
            for (int i = 0; i <= m - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
                        && down[i][j + k - 1] >= k) {
                        return k * k;
                    }
                }
            }
        }
        return 0;
    }
}