LeetCode 1139中等动态规划
最大的以 1 为边界的正方形 图解题解
这道题到底在问什么
把要求抠清楚:我们要的是「以 1 为边界」的正方形,也就是上下左右四条边整圈都是 1,内部填什么都行。返回值是这个正方形的元素个数,边长是 k 就返回 k 乘 k,不是返回 k 本身。提示里网格最大 100 乘 100,每个格子只会是 0 或 1。注意经典样例里中间是个 0 照样算数,因为我们只看边框。
- 输入
- grid = [[1,1,1],[1,0,1],[1,1,1]]
- 输出
- 9(边框整圈是 1,中间那个 0 不影响)
- 输入
- grid = [[1,1,0,0]]
- 输出
- 1(只能凑出一个 1×1)
- 输入
- 本节演示 4×4 网格
- 输出
- 9
最优解：一步一步想明白
- 3记住这条:把每个格子向下、向右的连续 1 个数先算好,四条边是否全 1 就靠四个角的计数和 k 比大小。边长从大到小,首次命中即最大。
- 4这是一张 4×4 网格,行号 i、列号 j。左上角 (0,0) 和右下角 (3,3) 是 0,其余十四格都是 1。还没处理的格子先显示原始的 0 或 1,处理过的格子会换成「向下连续数、向右连续数」这两个值。我们要找的最大正方形,答案会落在 9。
- 5第 3 行第 3 列是 0,连续 1 的链子在这里断掉,向下、向右都记 0。
- 6第 3 行第 2 列是 1。下面已经到头,下面没有格子(算作 0),所以向下只算自己这 1 个;向右接着右边那格的 0 个,连上自己向右连续 1 个。
- 7第 3 行第 1 列是 1。下面已经到头,下面没有格子(算作 0),所以向下只算自己这 1 个;向右接着右边那格的 1 个,连上自己向右连续 2 个。
- 8第 3 行第 0 列是 1。下面已经到头,下面没有格子(算作 0),所以向下只算自己这 1 个;向右接着右边那格的 2 个,连上自己向右连续 3 个。
- 9第 2 行第 3 列是 1。向下接着下面那格的 0 个,连上自己向下连续 1 个;右边已经到头,右边没有格子(算作 0),所以向右只算自己这 1 个。
- 10第 2 行第 2 列是 1。向下接着下面那格的 1 个,连上自己向下连续 2 个;向右接着右边那格的 1 个,连上自己向右连续 2 个。
- 11第 2 行第 1 列是 1。向下接着下面那格的 1 个,连上自己向下连续 2 个;向右接着右边那格的 2 个,连上自己向右连续 3 个。
- 12第 2 行第 0 列是 1。向下接着下面那格的 1 个,连上自己向下连续 2 个;向右接着右边那格的 3 个,连上自己向右连续 4 个。
- 13第 1 行第 3 列是 1。向下接着下面那格的 1 个,连上自己向下连续 2 个;右边已经到头,右边没有格子(算作 0),所以向右只算自己这 1 个。
- 14第 1 行第 2 列是 1。向下接着下面那格的 2 个,连上自己向下连续 3 个;向右接着右边那格的 1 个,连上自己向右连续 2 个。
- 15第 1 行第 1 列是 1。向下接着下面那格的 2 个,连上自己向下连续 3 个;向右接着右边那格的 2 个,连上自己向右连续 3 个。
- 16第 1 行第 0 列是 1。向下接着下面那格的 2 个,连上自己向下连续 3 个;向右接着右边那格的 3 个,连上自己向右连续 4 个。
- 17第 0 行第 3 列是 1。向下接着下面那格的 2 个,连上自己向下连续 3 个;右边已经到头,右边没有格子(算作 0),所以向右只算自己这 1 个。
- 18第 0 行第 2 列是 1。向下接着下面那格的 3 个,连上自己向下连续 4 个;向右接着右边那格的 1 个,连上自己向右连续 2 个。
- 19第 0 行第 1 列是 1。向下接着下面那格的 3 个,连上自己向下连续 4 个;向右接着右边那格的 2 个,连上自己向右连续 3 个。
- 20第 0 行第 0 列是 0,连续 1 的链子在这里断掉,向下、向右都记 0。
- 21十六个格子全部处理完。现在每格都写着向下、向右两个连续 1 的个数,0 的格子是 ↓0 →0。接下来从最大的边长开始,看看能不能拼出一个四边全 1 的正方形。
- 22先试最大的边长 4,整张网格只有一个左上角 (0,0)。可它本身就是 0,向右、向下的连续计数都是 0,上边都凑不齐,边长 4 直接出局。
- 23边长缩到 3。第一个左上角还是 (0,0),它是 0,连第一条边都开不了头,跳过,换下一个左上角。
- 24换到左上角 (0,1),它是 1,可以开工。先查上边,这条边占第 0 行的列 1 到 3,正好是从 (0,1) 向右数 3 格。看它的向右计数 right 是 3,不小于 3,说明这 3 格全是 1,上边过关。
- 25再查左边,这条边占第 1 列的行 0 到 2,是从 (0,1) 向下数 3 格。看它的向下计数 down 是 4,比 3 还多,这 3 格当然全是 1,左边也过关。
- 26接着查下边。下边的起点是左下角 (2,1),这条边从它向右数 3 格。看 (2,1) 的向右计数 right 是 3,不小于 3,下边全是 1,过关。注意下边看的是左下角,别看错成左上角。
- 27最后查右边。右边的起点是右上角 (0,3),从它向下数 3 格。看 (0,3) 的向下计数 down 是 3,正好够 3,右边全是 1。四条边全部通过,边长 3 的正方形找到了。
- 28把这圈边框点亮:左上角 (0,1),覆盖第 0 到 2 行、第 1 到 3 列。整圈 8 个边框格全是 1,里面那格是什么都无所谓。因为我们是从大边长往小试的,4 凑不出、3 第一个命中,这个 3 就是最大的。它覆盖的 9 个格子面积是 3 乘 3 等于 9,这就是答案。
⚠️ 容易写错的地方
✗ 错：以为正方形内部也必须全是 1
✓ 对：只要四条边整圈是 1,内部是 0 也算
题目要的是「以 1 为边界」,经典样例中间就是 0 照样返回 9;判断时只查边框,别去管内部
✗ 错：返回边长 k,或从小边长往大枚举
✓ 对：返回面积 k×k;边长从大往小枚举,第一个命中即最大
要的是元素个数,所以是 k 乘 k;从大往小试能在首次命中时直接返回,省去比较谁更大
✗ 错：四条边都拿左上角的计数去查
✓ 对：上、左看左上角,下边看左下角,右边看右上角
一条边全 1 要由它「起点角」的连续计数保证:下边起点是左下角 (i+k-1,j),右边起点是右上角 (i,j+k-1),下标算错就查错了边
完整代码（Python / C++ / Java）
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 0C++
#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;
}
}复杂度
时间
O(m·n·min(m,n))
预处理两张表是 O(m·n)。枚举阶段:边长 k 有 min(m,n) 种,每种要扫 O(m·n) 个左上角,每个左上角靠预处理的计数 O(1) 查四条边。方阵时约为 O(n³),n ≤ 100 完全够用
空间
O(m·n)
按峰值算:down、right 两张和网格同样大的表,都是 m×n,空间是 O(m·n);若网格是 n×n 方阵就是 O(n²)。没有递归,不额外吃栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大的以 1 为边界的正方形 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么要预处理 down 和 right 两张表?+
它们把「一条边是否全 1」从逐格检查的 O(k) 降到一次比大小的 O(1)。down[i][j] 是从该格向下连续 1 的个数,right[i][j] 是向右连续 1 的个数,都含自己。一条长度 k 的边全是 1,等价于它起点角的对应计数 ≥ k。没有这两张表,每验一条边都要走 k 格,总复杂度会到 O(n⁴);有了它们就是 O(n³)。
四条边分别看哪个角的计数?+
对左上角 (i,j) 边长 k 的正方形:上边看左上角的 right[i][j],左边看左上角的 down[i][j],下边看左下角的 right[i+k-1][j],右边看右上角的 down[i][j+k-1]。四个都 ≥ k 才算四边全 1。关键是下边、右边的起点不是左上角,下标里的 i+k-1、j+k-1 别写错。
复杂度能再压吗?+
这道题 O(n³) 是常见且足够的解法,n ≤ 100 时几十万次运算很快。预处理两张表是 O(n²),瓶颈在三重枚举。实际工程里这个量级无需再优化;真要面试加分,可以说清「从大边长往小枚举、首次命中即返回」这个早停,能避免枚举所有更小的边长。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大的以 1 为边界的正方形 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。