给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
自己的方法是优化一半的方法,使用单调栈更好
class Solution:
def largestRectangleArea(self, heights) -> int:
ln = len(heights)
heights = heights[::-1]
begins_l = [i for i in range(ln)]
begins_r = [i for i in range(ln)]
if ln ==0: return 0
max_area = max(heights)
for i,height in enumerate(heights):
if height*ln<=max_area:
continue
if i > 0 and heights[i-1]>=height:
begin_l = begins_l[i-1]
begin_r = begins_r[i-1]
else:
begin_l = i
begin_r = i
while begin_l>0:
if height<=heights[begin_l-1]:
begin_l-=1
else:
break
begins_l[i] = begin_l
if (ln-begin_l)*height<=max_area:
continue
while begin_r<ln-1:
if height<=heights[begin_r+1]:
begin_r+=1
else:
break
begins_r[i] = begin_r
#print(begin_r,begin_l,max_area)
max_area = max(max_area, (begin_r-begin_l+1)*height)
return max_area
原文:https://www.cnblogs.com/Lzqayx/p/13680894.html