Maximal Square - LeetCode 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.
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.length n == matrix[i].length 1 <= m, n <= 300 matrix[i][j] is ‘0’ or ‘1’.
- code
public class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
int[][] dp = new int[rows + 1][cols + 1];
int maxsqlen = 0;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
if (matrix[i-1][j-1] == '1'){
dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
maxsqlen = Math.max(maxsqlen, dp[i][j]);
}
}
}
return maxsqlen * maxsqlen;
}
}
- code
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
rows, cols = len(matrix) + 1, len(matrix[0]) + 1
dp = [0] * cols # 011122, after third row of eg1
max_length = -1
pre = 0 # previous row's dp[col - 1]
for row in range(1, rows):
for col in range(1, cols):
temp = dp[col]
if matrix[row-1][col-1] == "1":
dp[col] = min(dp[col], dp[col-1], pre) + 1
else:
dp[col] = 0
pre = temp
max_length = max(max_length, dp[col])
return max_length ** 2
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
self.maxm = -1
def cal(histogram):
# 3 1 3 2 2
stack = [-1]
maxs = -1
histogram.append(-1) # force to cal the end
for i, cur in enumerate(histogram):
while stack[-1] != -1 and cur <= histogram[stack[-1]]:
last_i = stack.pop()
length = min(i - stack[-1] - 1, histogram[last_i])
maxs = max(maxs, length * length)
stack.append(i)
self.maxm = max(self.maxm, maxs)
return
last_row = [0] * len(matrix[0])
for row in matrix:
for col_index in range(len(row)):
if row[col_index] != "0":
row[col_index] = last_row[col_index] + 1
else:
row[col_index] = 0
last_row = row
cal(row)
return self.maxm