栈与队列 解题模板

适用场景

• 栈：括号匹配、表达式求值、单调栈找下一个更大/更小元素

• 队列：BFS、滑动窗口、层次遍历

• 单调栈/队列：维护局部极值

通用模板

括号匹配

 
stack = []
 
pairs = {')': '(', ']': '[', '}': '{'}
 
for c in s:
 
    if c in pairs:
 
        if not stack or stack.pop() != pairs[c]:
 
            return False
 
    else:
 
        stack.append(c)
 
return not stack
 

单调栈（找下一个更大元素）

 
# 递减栈（栈顶最小）
 
stack = []
 
res = [0] * len(nums)
 
for i, num in enumerate(nums):
 
    while stack and num > nums[stack[-1]]:
 
        j = stack.pop()
 
        res[j] = i - j  # 或 num
 
    stack.append(i)
 

单调队列（滑动窗口最大值）

 
from collections import deque
 
dq = deque()  # 存下标，递减
 
res = []
 
for i, num in enumerate(nums):
 
    while dq and dq[0] < i - k + 1: dq.popleft()
 
    while dq and nums[dq[-1]] < num: dq.pop()
 
    dq.append(i)
 
    if i >= k-1: res.append(nums[dq[0]])
 

复杂度总结

模式	时间	空间	典型题
栈匹配	O(n)	O(n)	有效括号
单调栈	O(n)	O(n)	每日温度、最大矩形
单调队列	O(n)	O(k)	滑动窗口最大值
双栈模拟队列	均摊O(1)	O(n)	用栈实现队列

关键要点

• 单调栈存下标不是存值（方便计算距离）

• 栈模拟时注意空栈边界

• 单调队列 pop 前检查是否超出窗口

→ 查看该分类题目：LeetCode学习路线图 > 三、栈与队列

---

关联题型

关联题型	常见结合方式	典型题目
二叉树遍历	栈实现迭代遍历	94中序, 144前序, 145后序
动态规划	单调栈优化DP	84柱状图最大矩形
回溯	栈保存路径状态	77组合