柱状图最大矩形、每日温度、滑动窗口最大值——单调数据结构的威力
单调栈和单调队列是维护序列中元素单调性的数据结构。它们的核心思想是：当一个新元素到来时，移除所有"不再有用"的旧元素，只保留对未来有用的信息。
题目描述：给定一个非负整数数组 heights，表示柱状图中各个柱子的高度，每个柱子宽度为1，求柱状图中能勾勒出的最大矩形面积。
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = [] # 单调递增栈（存索引）
max_area = 0
heights.append(0) # 哨兵，确保所有柱子都会被弹出
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
# 左边界: 栈顶(弹出后) 或 -1(栈空)
left = stack[-1] if stack else -1
width = i - left - 1
max_area = max(max_area, height * width)
stack.append(i)
heights.pop() # 恢复
return max_area时间复杂度：O(n)，空间复杂度：O(n)
题目描述：给定一个整数数组 temperatures，表示每天的温度，返回数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
answer = [0] * n
stack = [] # 单调递减栈（存索引）
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
prev = stack.pop()
answer[prev] = i - prev
stack.append(i)
return answer时间复杂度：O(n)，空间复杂度：O(n)
题目描述：给定一个数组和滑动窗口大小 k，返回每个窗口中的最大值。
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
dq = deque() # 单调递减队列（存索引）
result = []
for i, num in enumerate(nums):
# 1. 维护单调性：移除队尾比当前小的
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
# 2. 移除过期元素
if dq[0] <= i - k:
dq.popleft()
# 3. 记录结果
if i >= k - 1:
result.append(nums[dq[0]])
return result时间复杂度：O(n)，空间复杂度：O(k)
# 下一个更大元素（单调递减栈）
def next_greater(nums):
n = len(nums)
result = [-1] * n
stack = [] # 递减栈，存索引
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
result[stack.pop()] = num
stack.append(i)
return result
# 变体: 循环数组的下一个更大元素 (LC 503)
def next_greater_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
result[stack.pop()] = nums[i % n]
if i < n:
stack.append(i)
return result# 柱状图最大矩形（单调递增栈）
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0] # 哨兵
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
max_area = max(max_area, height * (i - left - 1))
stack.append(i)
return max_area# 滑动窗口最大值（单调递减队列）
from collections import deque
def sliding_max(nums, k):
dq = deque()
result = []
for i, num in enumerate(nums):
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return resultLC 85 是 LC 84 的2D版本——给一个0/1矩阵，求只含1的最大矩形面积。
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix: return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
# 复用LC 84的单调栈
stack = []
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
max_area = max(max_area, height * (i - left - 1))
stack.append(i)
return max_area