leetcode 84 Largest Rectangle in Histogram
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.Example:
Input: [2,1,5,6,2,3]
Output: 10
求最大的矩形面积。 可以用一个单调栈实现,例如最开始2入栈, 因为1<2, 故2出栈,1入栈,再5,6分别入栈,然后是2, 因为2<6, 6出栈,计算面积, 这样一直计算, 时间复杂度为O(n)
代码可以参考:
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
if len(heights)==0:
return 0
if len(heights)==1:
return heights[0]
res=0
s=[]
heights.append(0)
s.append(-1)
s.append(0)
for i in range(1,len(heights)):
while len(s)>1 and heights[i]<heights[s[len(s)-1]]:
temp=s[len(s)-1]
if res<heights[temp]*(i-s[len(s)-2]-1):
res=heights[temp]*(i-s[len(s)-2]-1)
s.pop()
s.append(i)
return res