题目描述
给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
示例 1:
输入:
[
[1,0,1],
[0,0,1],
[0,0,1]
]
输出: [1,0,2]
解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
示例 2:
输入:
[
[0,1,1],
[1,0,1],
[1,1,0]
]
输出: [0,0,1]
提示：
matrix.length == matrix[0].length <= 200
解法
方法一：预处理 + 枚举
我们可以预处理出每个位置 $(i, j)$ 向下和向右的连续 $0$ （黑色像素）的个数，记为 $down[i][j]$ 和 $right[i][j]$。递推公式如下：
$$
down[i][j] = \begin{cases}
down[i + 1][j] + 1, & matrix[i][j] = 0 \text{ 且 } i + 1 < n \
1, & matrix[i][j] = 0 \text{ 且 } i + 1 = n \
0, & matrix[i][j] = 1
\end{cases}
$$
$$
right[i][j] = \begin{cases}
right[i][j + 1] + 1, & matrix[i][j] = 0 \text{ 且 } j + 1 < n \
1, & matrix[i][j] = 0 \text{ 且 } j + 1 = n \
0, & matrix[i][j] = 1
\end{cases}
$$
需要注意的是，由于 $down[i][j]$ 依赖于 $down[i + 1][j]$，而 $right[i][j]$ 依赖于 $right[i][j + 1]$，所以，我们在预处理 $down[i][j]$ 和 $right[i][j]$ 时，是从大到小枚举 $i$ 和 $j$ 的。
接下来，我们从大到小枚举正方形的边长 $k$，从小到大枚举正方形的左上角位置 $(i, j)$，如果满足 $down[i][j] \ge k$ 且 $right[i][j] \ge k$ 且 $right[i + k - 1][j] \ge k$ 且 $down[i][j + k - 1] \ge k$，说明我们找到了一个边长最大为 $k$ 且左上角位置为 $(i, j)$ 的黑方阵，直接返回 $[i, j, k]$ 即可。
如果枚举完所有的正方形都没有满足条件的，那么返回空数组。
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 是方阵的边长。
相似题目：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution:
def findSquare(self, matrix: List[List[int]]) -> List[int]:
n = len(matrix)
down = [[0] * n for _ in range(n)]
right = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
if matrix[i][j] == 0:
down[i][j] = down[i + 1][j] + 1 if i + 1 < n else 1
right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1
for k in range(n, 0, -1):
for i in range(n - 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 [i, j, k]
return []
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
public int[] findSquare(int[][] matrix) {
int n = matrix.length;
int[][] down = new int[n][n];
int[][] right = new int[n][n];
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (matrix[i][j] == 0) {
down[i][j] = i + 1 < n ? down[i + 1][j] + 1 : 1;
right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
}
}
}
for (int k = n; k > 0; --k) {
for (int i = 0; i <= n - 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 new int[] {i, j, k};
}
}
}
}
return new int[0];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | class Solution {
public:
vector<int> findSquare(vector<vector<int>>& matrix) {
int n = matrix.size();
int down[n][n];
int right[n][n];
memset(down, 0, sizeof(down));
memset(right, 0, sizeof(right));
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (matrix[i][j] == 0) {
down[i][j] = i + 1 < n ? down[i + 1][j] + 1 : 1;
right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
}
}
}
for (int k = n; k > 0; --k) {
for (int i = 0; i <= n - 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 {i, j, k};
}
}
}
}
return {};
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | func findSquare(matrix [][]int) []int {
n := len(matrix)
down := make([][]int, n)
right := make([][]int, n)
for i := range down {
down[i] = make([]int, n)
right[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if matrix[i][j] == 0 {
down[i][j], right[i][j] = 1, 1
if i+1 < n {
down[i][j] += down[i+1][j]
}
if j+1 < n {
right[i][j] += right[i][j+1]
}
}
}
}
for k := n; k > 0; k-- {
for i := 0; i <= n-k; i++ {
for 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 []int{i, j, k}
}
}
}
}
return []int{}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | function findSquare(matrix: number[][]): number[] {
const n = matrix.length;
const down: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
const right: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = n - 1; i >= 0; --i) {
for (let j = n - 1; j >= 0; --j) {
if (matrix[i][j] === 0) {
down[i][j] = i + 1 < n ? down[i + 1][j] + 1 : 1;
right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
}
}
}
for (let k = n; k > 0; --k) {
for (let i = 0; i <= n - k; ++i) {
for (let 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 [i, j, k];
}
}
}
}
return [];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
func findSquare(_ matrix: [[Int]]) -> [Int] {
let n = matrix.count
var down = Array(repeating: Array(repeating: 0, count: n), count: n)
var right = Array(repeating: Array(repeating: 0, count: n), count: n)
for i in stride(from: n - 1, through: 0, by: -1) {
for j in stride(from: n - 1, through: 0, by: -1) {
if matrix[i][j] == 0 {
down[i][j] = (i + 1 < n) ? down[i + 1][j] + 1 : 1
right[i][j] = (j + 1 < n) ? right[i][j + 1] + 1 : 1
}
}
}
for k in stride(from: n, through: 1, by: -1) {
for i in 0...(n - k) {
for j in 0...(n - k) {
if down[i][j] >= k && right[i][j] >= k &&
right[i + k - 1][j] >= k && down[i][j + k - 1] >= k {
return [i, j, k]
}
}
}
}
return []
}
}
|