stack = []for item in items: if "需要入栈": stack.append(item) else: # 出栈处理 val = stack.pop()
单调栈模板（找下一个更大元素）
def next_greater_element(nums): n = len(nums) res = [-1] * n stack = [] # 存索引 for i in range(n): # 当前元素比栈顶大：找到"下一个更大元素" while stack and nums[stack[-1]] < nums[i]: idx = stack.pop() res[idx] = nums[i] stack.append(i) return res
单调栈变体：
找下一个更大元素 → 单调递减栈（栈底到栈顶递减）
找下一个更小元素 → 单调递增栈（栈底到栈顶递增）
找上一个更大元素 → 反向遍历
柱状图中最大矩形（单调栈经典应用）
def largest_rectangle_area(heights): stack = [] # 存索引，维护递增栈 heights = [0] + heights + [0] # 加哨兵，避免空栈判断 max_area = 0 for i in range(len(heights)): while stack and heights[stack[-1]] > heights[i]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area
三、堆（优先队列）
Python 堆操作（heapq 模块）
import heapq# 最小堆heap = []heapq.heappush(heap, val) # 入堆min_val = heapq.heappop(heap) # 弹出最小值min_val = heap[0] # 查看最小值（不弹出）# 大根堆：存负值heapq.heappush(heap, -val)max_val = -heapq.heappop(heap)# 将数组堆化 O(n)heapq.heapify(arr)# Top K 最大：用最小堆维护def top_k_largest(nums, k): heap = [] for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) return heap[0] # 第 k 大
经典应用：数据流的中位数（双堆）
from heapq import heappush, heappopclass MedianFinder: def __init__(self): # 大根堆存较小一半（Python 无大根堆，存负值） self.small = [] # max-heap # 小根堆存较大一半 self.large = [] # min-heap def add_num(self, num): heappush(self.small, -num) # 确保 small 中所有元素 <= large 中所有元素 if self.small and self.large and (-self.small[0]) > self.large[0]: val = -heappop(self.small) heappush(self.large, val) # 平衡两堆大小 if len(self.small) > len(self.large) + 1: val = -heappop(self.small) heappush(self.large, val) if len(self.large) > len(self.small): val = heappop(self.large) heappush(self.small, -val) def find_median(self): if len(self.small) > len(self.large): return -self.small[0] return (-self.small[0] + self.large[0]) / 2.0