数据结构类型:栈
时间复杂度:O(N)
空间复杂度:O(N)
代码实现:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
area = 0
for i in range(len(heights)):
index = i
while stack and stack[-1][1] > heights[i]:
last_i, last_h = stack.pop()
index = last_i
area = max(area, last_h * (i - last_i))
stack.append([index, heights[i]])
for i, h in stack:
area = max(area, (len(heights) - i) * h)
return area