单调栈算法
1. 核心思想
单调栈是一种特殊的栈结构，栈内元素保持单调性（递增或递减）。主要用于解决寻找下一个更大/更小元素的问题。
2. 适用场景
- 寻找每个元素左/右侧第一个比它大/小的元素
- 柱状图中最大矩形面积
- 接雨水问题
- 股票价格跨度
3. 模板代码
单调递减栈（找下一个更大元素）
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n # 初始化结果数组
stack = [] # 存储索引
for i in range(n):
# 当前元素大于栈顶元素时，栈顶元素找到了下一个更大元素
while stack and nums[i] > nums[stack[-1]]:
index = stack.pop()
result[index] = nums[i]
stack.append(i)
return result
单调递增栈（找下一个更小元素）
def nextSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
# 当前元素小于栈顶元素时，栈顶元素找到了下一个更小元素
while stack and nums[i] < nums[stack[-1]]:
index = stack.pop()
result[index] = nums[i]
stack.append(i)
return result
4. 经典例题
例1: 每日温度
def dailyTemperatures(temperatures):
"""
给定一个列表，返回需要等待多少天才能遇到更高的温度
"""
n = len(temperatures)
result = [0] * n
stack = []
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_index = stack.pop()
result[prev_index] = i - prev_index
stack.append(i)
return result
例2: 柱状图中最大矩形
def largestRectangleArea(heights):
"""
使用单调递增栈
"""
stack = []
max_area = 0
heights.append(0) # 哨兵，确保所有元素都出栈
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * w)
stack.append(i)
return max_area