Problem
Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
https://leetcode.com/problems/maximal-square/
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
Example 2:
Input: matrix = [["0","1"],["1","0"]]
Output: 1
Example 3:
Input: matrix = [["0"]]
Output: 0
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j] is '0' or '1'.
Test Cases
1
2
| class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
|
solution_test.py1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| import pytest
from solution import Solution
@pytest.mark.parametrize('matrix, expected', [
([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]], 4),
([["0","1"],["1","0"]], 1),
([["0"]], 0),
([["1","0","1","0"],["1","0","1","1"],["1","0","1","1"],["1","1","1","1"]], 4),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, matrix, expected):
assert sol.maximalSquare(matrix) == expected
|
Thoughts
对于任意格子 (i, j)（0 ≤ i < m、0 ≤ j < n），定义三个状态量：
h(i, j) 表示以格子 (i, j) 为最右端的连续 '1' 的个数。v(i, j) 表示以格子 (i, j) 为最下端的连续 '1' 的个数。s(i, j) 表示以格子 (i, j) 为右下角的全 '1' 正方形的边长。
可得状态转移方程：
当 matrix[i][j] = '0' 时：
⎩⎨⎧h(i,j)=0v(i,j)=0s(i,j)=0
当 matrix[i][j] = '1' 时：
⎩⎨⎧h(i,j)=h(i,j−1)+1v(i,j)=v(i−1,j)+1s(i,j)=min⎩⎨⎧s(i−1,j−1)+1h(i,j)v(i,j)
边界值 h(i, -1) = v(-1, j) = s(-1, -1) = s(i, -1) = s(-1, j) = 0。递推过程中记录最大的 s 值，取平方则为题目所求结果。
根据状态转移方程的依赖关系，在递推过程中只需要保留一行的 v 和 s 值，只需要保留当前行的一个 h 值。
整体时间复杂度 O(m * n)，空间复杂度 O(n)。
Code
solution.py1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def maximalSquare(self, matrix: list[list[str]]) -> int:
m = len(matrix)
n = len(matrix[0])
v = [0] * n
s = [0] * n
max_s = 0
for i in range(m):
h = 0
prev_s = 0
for j in range(n):
if matrix[i][j] == '0':
h = 0
v[j] = 0
prev_s, s[j] = s[j], 0
else:
h += 1
v[j] += 1
prev_s, s[j] = s[j], min(prev_s + 1, h, v[j])
if s[j] > max_s:
max_s = s[j]
return max_s * max_s
|
