0%

LeetCode: 84. Largest Rectangle in Histogram

利用stack保存下标,这些下标对应的高度是单调递增的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
heights.append(0)
ret = 0
stack =[]
for i, h in enumerate(heights):
while stack and heights[stack[-1]]>h:
idx = stack.pop()
height = heights[idx]
w = i if not stack else i-stack[-1]-1
ret = max(ret, height*w)
stack.append(i)
return ret