问题描述
我正在调试以下问题并发布问题声明和代码。 我的问题是，我认为for循环（对于范围（m）中的i和xrange（n）中的j）是不正确的，因为它只考虑顶行的矩形？ 如果我错了，请随时纠正我。 谢谢。
给定填充0和1的2D二进制矩阵，找到包含所有1的最大矩形并返回其区域。
def maximalRectangle(self, matrix):
if not matrix:
return 0
m, n, A = len(matrix), len(matrix[0]), 0
height = [0 for _ in range(n)]
for i in range(m):
for j in xrange(n):
height[j] = height[j]+1 if matrix[i][j]=="1" else 0
A = max(A, self.largestRectangleArea(height))
return A
def largestRectangleArea(self, height):
height.append(0)
stack, A = [0], 0
for i in range(1, len(height)):
while stack and height[stack[-1]] > height[i]:
h = height[stack.pop()]
w = i if not stack else i-stack[-1]-1
A = max(A, w*h)
stack.append(i)
return A
1楼
我的Java解决方案：
public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int rows = matrix.length;
int cols = matrix[0].length;
int[][] length = new int[rows][cols];
int result = 0;
for (int i = 0; i < rows; i++) {
length[i][0] = Character.getNumericValue(matrix[i][0]);
result = Math.max(result, length[i][0]);
}
for (int j = 0; j < cols; j++) {
length[0][j] = Character.getNumericValue(matrix[0][j]);
result = Math.max(result, length[0][j]);
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j] == '1') {
length[i][j] = Math.min(
Math.min(length[i - 1][j], length[i][j - 1]),
length[i - 1][j - 1]) + 1;
result = Math.max(result, length[i][j] * length[i][j]);
}
}
}
return result;
}
}