我正在解决以下问题并发布问题陈述和代码。我的问题是,我认为循环(for i in range(m) and for j in xrange(n))不正确,因为它只考虑了从顶部行开始的矩形?如果我错了,请随意纠正我。谢谢。
给定一个填充有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