单调栈是特殊栈结构，栈中元素保持单调递增或递减，用于快速查找下一个更大/更小元素。
核心特点
- 单调递增栈：栈底到栈顶逐渐增大
- 单调递减栈：栈底到栈顶逐渐减小
典型应用
| 应用 | 说明 |
|---|---|
| 下一个更大元素 | 单调递增栈 |
| 下一个更小元素 | 单调递减栈 |
| 前一个更大/更小元素 | 方向相反 |
| 柱状图最大矩形 | 单调递增栈 |
| 接雨水问题 | 单调递减栈 |
代码模板
def next_greater_element(nums):
result = [-1] * len(nums)
stack = [] # 单调递增栈
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
result[stack.pop()] = num
stack.append(i)
return result时间复杂度
O(n) — 每个元素最多入栈出栈各一次