https://leetcode.com/problems/largest-rectangle-in-histogram/
- 单调栈: 寻找左右两边第一个比自己小的柱子。右边通过单调栈外的元素实现，左边通过单调栈里的元素实现。栈顶，栈顶的下一个元素，即将入栈的元素：这三个元素组成了最大面积的高度和宽度
- 迭代的时候，当一个小的高度出现时，可以更新比他大的柱子和他自己构成的矩形面积了，此时把栈保存的pop出来计算
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时间复杂度：O(n)
空间复杂度：O(n)
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时间复杂度：O()
空间复杂度：O()
- 双指针: 找每个柱子左右两边第一个小于该柱子的柱子