class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# 输入数组首尾各补上一个0
heights = [0] + heights + [0]
stack = [0]
result = 0
for i in range(1, len(heights)):
# 单调栈: 找左右第一个比自己小的. 更新过程中，作为右边，如果比栈顶左边的元素小，则出栈计算结果
while stack and heights[i] < heights[stack[-1]]:
mid_height = heights[stack[-1]]
stack.pop()
if stack:
# 左边比自己小的，则是剩余栈里的栈顶
area = (i - stack[-1] - 1) * mid_height
result = max(area, result)
stack.append(i)
return result
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
stack = [] # 单调栈
next_smaller_left = [0] * n
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
next_smaller_left[i] = stack[-1] + 1
stack.append(i)
stack = []
next_smaller_right = [n - 1] * n
for i in range(n-1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
next_smaller_right[i] = stack[-1] - 1
stack.append(i)
res = heights[0]
for i in range(n):
height = heights[i]
width = next_smaller_right[i] - next_smaller_left[i] + 1
area = height * width
res = max(res, area)
return res