算法分析
这里仅讨论满足要求的最大正方形的边长
定义 $l_{ij}$ 表示从 $(i, j)$ 向左能延伸的距离,即向左有多少个连续的 $1$,同理定义 $r_{ij}$、$u_{ij}$、$b_{ij}$ 表示向右、向上、向下的延伸距离。这些距离可以 $O(n^2)$ 预处理得到。
在此基础上,依次考虑矩阵的每一条向右的对角线,并计算左上角和右下角均位于该对角线上的最大正方形。原问题即从二维简化至一维。故对于特定对角线,令 $f_i = \min(b_i, r_i)$ 表示其中第 $i$ 格向右下方的延伸距离,令 $g_i = \min(u_i, l_i)$ 表示向左上方的延伸距离,一维问题等价于求满足下来三个条件的 $\max\{j-i+1\}$。
- $i \leqslant j$
- $i+f_i-1 \geqslant j$
- $j-g_i+1 \leqslant i$
具体地,可从左到右枚举 $j$,求出能与当前 $j$ 组成正方形的最小 $i$,对于这部分可以用线段树来维护。
总的时间复杂度为 $O(n^2\log n)$。
事实上,也可以做到 $O(n^2)$,这里就留给读者了