我试图找到最大面积直方图,但我想跟踪最大矩形的高度和宽度。我尝试了不同的方法初始化和跟踪全局宽度,但都做不到。在
这是我写的最大面积直方图的代码。 用这个视频来编码。https://www.youtube.com/watch?v=RVIh0snn4Qc&t=888s
class Solution:
def largestRectangleArea(self, hist):
stack=[]; i=0; area=0
while i<len(hist):
if stack==[] or hist[i]>hist[stack[len(stack)-1]]:
stack.append(i)
else:
curr=stack.pop()
width=i if stack==[] else i-stack[len(stack)-1]-1
area=max(area,width*hist[curr])
i-=1
i+=1
while stack!=[]:
curr=stack.pop()
width=i if stack==[] else len(hist)-stack[len(stack)-1]-1
area=max(area,width*hist[curr])
return area,
def maximalRectangle(self, matrix):
if matrix==[]: return 0
a=[0 for i in range(len(matrix[0]))]; maxArea=0
for i in range(len(matrix)):
for j in range(len(matrix[i])):
a[j]=a[j]+1 if matrix[i][j]=='1' else 0
maxArea=max(maxArea, self.largestRectangleArea(a)[0])
print (self.largestRectangleArea(a))
return maxArea
if __name__ == "__main__":
print( Solution().maximalRectangle([['1', '1', '0', '1', '0', '1'],
['0', '1', '0', '0', '1', '1'],
['1', '1', '1', '1', '0', '1'],
['1', '1', '1', '1', '0', '1']]))
用自己的实现替换内置的}的值是最好的(此时)。像这样:
max
操作-当获得更好的结果时,记住width
和{相关问题 更多 >
编程相关推荐