原题地址：https://leetcode.cn/problems/maximal-square/
题解
通过三个矩阵记录坐标(x,y)的状态：
- v1记录包括(x,y)在内的，向上连续的1的个数
- h1记录包括(x,y)在内的，向左连续的1的个数
- dp记录(x,y)为正方形右下角时的最大正方形边长
当(x,y)为1时，v1和h1并不难计算：
- v1[y][x]=v1[y-1][x]+1
- h1[y][x]=h1[y][x-1]+1
在如下两种情况下，dp[y][x]为1，即只能它自身构成一个边长为1的正方形
- 当x为0或y为0时
- 当dp[y-1][x-1]==0时（即它左上角的那个相邻元素为0）
其余情况下，dp[y][x]应当为如下三者中的最小值：
- v1[y][x]
- h1[y][x]
- dp[y-1][x-1]+1
每次取dp[y][x]的最大值，即为最大正方形的边长
时间复杂度：O(N)
空间复杂度：O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
fun maximalSquare(matrix: Array<CharArray>): Int {
val v1 = Array(matrix.size) { _ -> Array(matrix[0].size) { _ -> 0 } }
val h1 = Array(matrix.size) { _ -> Array(matrix[0].size) { _ -> 0 } }
val dp = Array(matrix.size) { _ -> Array(matrix[0].size) { _ -> 0 } }
var max = Int.MIN_VALUE
for (y in 0 until matrix.size) {
for (x in 0 until matrix[y].size) {
if (matrix[y][x] == '1') {
v1[y][x] = (if (y - 1 >= 0) v1[y - 1][x] else 0) + 1
h1[y][x] = (if (x - 1 >= 0) h1[y][x - 1] else 0) + 1
if (y == 0 || x == 0 || dp[y - 1][x - 1] == 0) {
dp[y][x] = 1
} else {
dp[y][x] = if (h1[y][x] <= v1[y][x]) h1[y][x] else v1[y][x]
dp[y][x] = if (dp[y - 1][x - 1] + 1 <= dp[y][x]) dp[y - 1][x - 1] + 1 else dp[y][x]
}
max = if (max < dp[y][x]) dp[y][x] else max
}
}
}
return max * max
}
}
|
