84.柱状图中最大的矩形
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
s = [0]
result = 0
heights.insert(0,0)
heights.append(0)
for i in range(1, len(heights)):
if heights[s[-1]] < heights[i]:
s.append(i)
elif heights[s[-1]] == heights[i]:
s.pop()
s.append(i)
else:
while s and heights[s[-1]] > heights[i]:
mid = s[-1]
s.pop()
if s:
min_left = s[-1]
min_right = i
area = (min_right-min_left-1)*heights[mid]
result = max(result, area)
s.append(i)
return result