单调栈与单调队列

第六章：单调栈与单调队列

你站在一排高楼之间，想知道每栋楼右边第一栋比它更高的楼在哪里。最朴素的做法是对每栋楼向右逐个扫描——这是 O(n²)。但如果你从右往左走，维护一个"越往栈底越高"的栈，每栋楼只需要弹出几个比它矮的元素就能找到答案。每个元素最多入栈一次、出栈一次，总共 O(n)。

这就是**单调栈（Monotone Stack）**的核心思想：通过维护栈内元素的单调性，将"为每个元素寻找某个方向上第一个满足某条件的元素"这类问题，从 O(n²) 降到 O(n)。

它的兄弟**单调队列（Monotone Deque）**则把同样的思想用在滑动窗口上：维护一个双端队列，队列内元素单调，从而在 O(1) 时间内获取窗口的最大值或最小值。

这两个数据结构看起来是"栈/队列的变种"，实际上它们是一种思维模式：利用单调性淘汰不可能成为答案的候选者，用空间换取暴力枚举的时间。掌握它们，你就掌握了一把解开大量看似复杂问题的钥匙。

Level 1 · 你需要知道的

1.1 单调栈的概念

单调栈是一个普通的栈，但我们在使用时维护一个不变量（invariant）：栈内元素从栈底到栈顶保持单调递增或单调递减。

为了维护这个不变量，每次新元素要入栈前，我们不断弹出栈顶那些违反单调性的元素，直到栈顶元素满足条件（或栈为空），然后再将新元素压入。

单调递增栈（栈底到栈顶递增）：

def monotone_increasing_stack(nums):
    """
    维护一个单调递增栈（从栈底到栈顶，值递增）。
    每次弹出意味着：被弹出的元素找到了右边第一个比它小的元素。
    """
    stack = []  # 存储索引
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] >= num:
            # nums[i] 是 nums[stack[-1]] 右边第一个更小的元素
            popped = stack.pop()
            # 处理 popped 对应的元素
        stack.append(i)

单调递减栈（栈底到栈顶递减）：

def monotone_decreasing_stack(nums):
    """
    维护一个单调递减栈（从栈底到栈顶，值递减）。
    每次弹出意味着：被弹出的元素找到了右边第一个比它大的元素。
    """
    stack = []  # 存储索引
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] <= num:
            # nums[i] 是 nums[stack[-1]] 右边第一个更大的元素
            popped = stack.pop()
            # 处理 popped 对应的元素
        stack.append(i)

关键洞察：栈里存的通常是索引而不是值。因为有了索引就可以查到值，但反过来不行（值可能重复）。而且很多题目需要用到"距离"（即索引之差）。

1.2 下一个更大元素（LeetCode #496, #503）

问题：给定一个数组，对于每个元素，找到它右边第一个比它大的元素。如果不存在，则记为 -1。

这是单调栈最经典的入门题。

def next_greater_element(nums: list[int]) -> list[int]:
    """
    对于 nums 中每个元素，找右边第一个比它大的值。
    思路：维护单调递减栈。当新元素比栈顶大时，栈顶的"下一个更大元素"就是当前新元素。
    
    时间复杂度：O(n)，每个元素最多入栈一次出栈一次
    空间复杂度：O(n)，栈的最大大小
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # 存索引，栈内对应的值从底到顶递减
    
    for i in range(n):
        # 当前元素比栈顶大 → 栈顶找到了答案
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    # 栈中剩余元素没有下一个更大值，保持 -1
    return result


# 测试
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums))  # [4, 2, 4, -1, -1]

执行过程详解（以 [2, 1, 2, 4, 3] 为例）：

最终 result = [4, 2, 4, -1, -1]。

LeetCode #496 — Next Greater Element I：

def next_greater_element_i(nums1: list[int], nums2: list[int]) -> list[int]:
    """
    nums1 是 nums2 的子集。对于 nums1 中每个元素，
    在 nums2 中找到它的位置，然后找右边第一个更大元素。
    
    思路：先用单调栈对 nums2 求出每个元素的下一个更大值，存入哈希表。
    然后 nums1 直接查表。
    """
    # 对 nums2 建立映射：值 -> 下一个更大值
    next_greater = {}
    stack = []
    
    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)
    
    # 栈中剩余元素没有更大值
    for num in stack:
        next_greater[num] = -1
    
    return [next_greater[num] for num in nums1]

1.3 每日温度（LeetCode #739）

问题：给定一个每日温度列表 temperatures，返回一个列表，其中每个位置的值表示要等几天才能遇到更高温度。如果之后没有更高温度，则为 0。

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """
    经典单调栈应用：找右边第一个更大元素的"距离"。
    
    维护单调递减栈（栈底到栈顶温度递减）。
    当新温度比栈顶高时，栈顶那天的答案 = 当前天 - 栈顶天。
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    n = len(temperatures)
    answer = [0] * n
    stack = []  # 存索引
    
    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            prev_day = stack.pop()
            answer[prev_day] = i - prev_day
        stack.append(i)
    
    return answer


# 测试
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))  # [1, 1, 4, 2, 1, 1, 0, 0]

为什么存索引而不是值：这道题需要计算"等几天"，即索引之差。如果栈里存的是温度值，你无法算出天数差距。

1.4 接雨水（LeetCode #42）——单调栈解法

问题：给定 n 个非负整数表示柱子高度（宽度为 1），计算下雨后能接多少水。

接雨水是面试中的超高频题，有多种解法（后面 Level 4 会全面对比）。这里先展示单调栈的做法。

单调栈思路：我们维护一个单调递减栈。当遇到一个比栈顶高的柱子时，说明栈顶的柱子被"夹"在了左右两个更高的柱子之间，形成了一个可以蓄水的凹槽。

def trap(height: list[int]) -> int:
    """
    接雨水 - 单调栈解法
    
    思路：维护单调递减栈。当 height[i] > height[stack[-1]] 时，
    栈顶形成凹槽的底部，弹出后新栈顶是左边界，i 是右边界。
    水量 = min(左高, 右高) - 底高) * 宽度
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    stack = []  # 存索引，对应高度单调递减
    water = 0
    
    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()  # 凹槽的底
            if not stack:
                break  # 左边没有边界了，无法蓄水
            left = stack[-1]  # 左边界
            # 宽度：两个边界之间的距离（不含边界本身）
            width = i - left - 1
            # 高度：两个边界中较矮的那个减去底部高度
            h = min(height[left], height[i]) - height[bottom]
            water += width * h
        stack.append(i)
    
    return water


# 测试
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap(height))  # 6

执行过程可视化（以 [0,1,0,2,1,0,1,3,2,1,2,1] 为例的关键步骤）：

柱子可视化：
        #
    #   ##
 #  ## ####
#_##_#_####_   （下划线表示水）

当 i=3 (高度=2)：
  栈: [1(h=1), 2(h=0)]
  弹出 2(底=0)，左=1(h=1)，右=3(h=2)
  水 += min(1,2)-0 * (3-1-1) = 1*1 = 1
  弹出 1(底=1)，栈空，break

当 i=7 (高度=3)：
  多次弹出积累大量水
  ...

1.5 柱状图中最大矩形（LeetCode #84）

问题：给定 n 个非负整数，表示柱状图中各个柱子的高度（宽度均为 1），找出柱状图中能勾勒出的最大矩形面积。

核心思想：对于每根柱子，以它的高度为矩形高度，能向左右延伸多远？延伸到第一个比它矮的柱子为止。所以问题转化为：对每个元素找左边第一个更小和右边第一个更小的位置。

def largest_rectangle_area(heights: list[int]) -> int:
    """
    柱状图中最大矩形 - 单调栈解法
    
    维护单调递增栈（栈底到栈顶高度递增）。
    当新柱子比栈顶矮时，栈顶柱子找到了右边界（当前柱子）
    和左边界（新的栈顶），可以计算以栈顶高度为高的矩形面积。
    
    技巧：在 heights 前后各加一个 0，避免边界判断。
    - 前面的 0 保证栈不会为空
    - 后面的 0 保证遍历结束时栈内所有柱子都被处理
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    heights = [0] + heights + [0]  # 哨兵
    stack = [0]  # 初始放入左哨兵
    max_area = 0
    
    for i in range(1, len(heights)):
        while heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            # 左边界：新栈顶；右边界：当前 i
            width = i - stack[-1] - 1
            max_area = max(max_area, h * width)
        stack.append(i)
    
    return max_area


# 测试
heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_area(heights))  # 10  (5和6组成的 5*2=10)

哨兵技巧的精妙之处：

1. 左哨兵（heights[0] = 0）：保证栈永远不为空，所以 stack[-1] 总是有效的左边界。
2. 右哨兵（heights[-1] = 0）：高度 0 比所有柱子都矮，所以遍历结束时栈内所有柱子都会被弹出处理。

没有哨兵的话，你需要在循环结束后额外处理栈中剩余元素，代码会复杂很多。

1.6 单调队列：滑动窗口最大值（LeetCode #239）

问题：给定一个数组和一个窗口大小 k，返回每个窗口的最大值。

暴力解法：对每个窗口遍历 k 个元素找最大值，O(nk)。

单调队列解法：维护一个双端队列（deque），队列中存储索引，对应的值从队头到队尾单调递减。队头永远是当前窗口的最大值。

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """
    滑动窗口最大值 - 单调队列解法
    
    维护单调递减的双端队列：
    1. 新元素入队前，从队尾弹出所有比它小的元素（它们不可能成为答案）
    2. 将新元素索引加入队尾
    3. 如果队头索引已经滑出窗口，从队头弹出
    4. 当窗口形成后（i >= k-1），队头就是当前窗口最大值
    
    时间复杂度：O(n)，每个元素最多入队一次出队一次
    空间复杂度：O(k)，队列最多存 k 个元素
    """
    dq = deque()  # 存索引，对应值单调递减
    result = []
    
    for i in range(len(nums)):
        # 1. 从队尾移除所有比当前元素小的（它们已无用）
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        
        # 2. 当前元素入队
        dq.append(i)
        
        # 3. 队头如果滑出窗口，移除
        if dq[0] <= i - k:
            dq.popleft()
        
        # 4. 当窗口完全形成后，记录最大值
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result


# 测试
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))  # [3, 3, 5, 5, 6, 7]

为什么队列中被弹出的元素"已无用"？

假设队列中有索引 j，现在来了索引 i（i > j），且 nums[i] >= nums[j]。那么：

• 在任何包含 j 的未来窗口中，i 也在这个窗口里（因为 i > j，i 比 j 晚离开窗口）
• 既然 nums[i] >= nums[j]，在这些窗口里 j 永远不可能是最大值
• 所以 j 可以安全丢弃

这就是单调队列的核心逻辑：淘汰不可能成为答案的候选者。

执行过程（nums = [1, 3, -1, -3, 5, 3, 6, 7]，k=3）：

1.7 常见错误总结

Level 2 · 它是怎么运行的

2.1 单调栈的时间复杂度分析：为什么是 O(n) 而不是 O(n²)

初学者常见疑问：外层循环是 O(n)，内层 while 循环不是又在弹栈吗？最坏情况会不会嵌套成 O(n²)？

答案是不会。这里需要用**均摊分析（Amortized Analysis）**来理解。

核心论证：每个元素最多入栈一次，最多出栈一次。

• 外层 for 循环执行 n 次，每次执行 stack.append(i)，所以总共有 n 次入栈操作。
• 内层 while 循环每次执行 stack.pop()，但 pop 的前提是栈里有东西。栈里最多只会有 n 个元素（因为只入栈 n 次）。
• 所以 pop 的总次数不超过 n。

总操作次数 = n 次入栈 + 最多 n 次出栈 = O(2n) = O(n)。

类比：想象一个旋转门，n 个人排队进去。每个人进门恰好一次，出门恰好一次。不管里面的"弹出"过程看起来多复杂，总操作次数不超过 2n。

形式化（聚合分析/Aggregate Analysis）：

设 T(n) 为总操作数。定义势能函数 Φ = 栈中元素个数。

对于第 i 次循环：

• 设 while 循环弹出 kᵢ 个元素
• 实际代价 cᵢ = kᵢ + 1（kᵢ 次 pop + 1 次 push）
• 势能变化 ΔΦᵢ = 1 - kᵢ（push 了 1 个，pop 了 kᵢ 个）
• 均摊代价 ĉᵢ = cᵢ + ΔΦᵢ = (kᵢ + 1) + (1 - kᵢ) = 2

每次循环的均摊代价恒为 2，总均摊代价 = 2n = O(n)。

2.2 单调栈 vs 暴力解法的对比

以"下一个更大元素"为例：

暴力解法：

def next_greater_brute(nums):
    """O(n²) 暴力：对每个元素向右扫描"""
    n = len(nums)
    result = [-1] * n
    for i in range(n):
        for j in range(i + 1, n):
            if nums[j] > nums[i]:
                result[i] = nums[j]
                break
    return result

性能对比：

暴力解法的问题：对于 [n, n-1, n-2, ..., 2, 1] 这样的递减序列，每个元素都找不到更大的，每次都要扫描到数组末尾，总比较次数 = n + (n-1) + ... + 1 = n(n-1)/2。

单调栈为什么快：它利用了传递性。如果 a < b < c，那么 a 的下一个更大元素不可能是 c（因为 b 先出现且 b > a）。暴力解法没有利用这个信息，单调栈通过维护栈的单调性隐式地编码了这个关系。

2.3 单调队列用 deque 实现的细节

Python 的 collections.deque 是基于双向链表块（block of doubly-linked list）实现的，两端操作都是 O(1)。

单调队列和普通队列的区别：

为什么不用 heapq（优先队列/堆）来做滑动窗口最大值？

堆可以在 O(log n) 时间内获取最大值，但有一个致命问题：删除不在堆顶的元素需要 O(n)。当窗口滑动，旧元素离开窗口时，如果它不在堆顶，你很难高效删除它。

虽然可以用"懒删除"技巧（标记为已删除，取堆顶时跳过），但最坏情况下堆的大小会膨胀到 O(n)，每次操作 O(log n)，总复杂度 O(n log n)。单调队列是严格 O(n) 的，更优。

2.4 环形数组的单调栈处理（取模技巧）

LeetCode #503 — Next Greater Element II：数组是环形的，最后一个元素的"下一个"是第一个元素。

def next_greater_elements_circular(nums: list[int]) -> list[int]:
    """
    环形数组的下一个更大元素。
    
    技巧：将数组"展开"为两倍长度，用取模访问原始位置。
    遍历 2n 个位置，但只对前 n 个记录答案。
    
    为什么遍历两遍就够了？因为每个元素最多需要"绕一圈"就能找到答案。
    如果绕一圈都找不到（即它是全局最大值），答案就是 -1。
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []
    
    for i in range(2 * n):
        # 用取模映射到原始索引
        while stack and nums[stack[-1]] < nums[i % n]:
            idx = stack.pop()
            result[idx] = nums[i % n]
        # 只在第一轮入栈（避免重复入栈）
        if i < n:
            stack.append(i)
    
    return result


# 测试
nums = [1, 2, 1]
print(next_greater_elements_circular(nums))  # [2, -1, 2]

nums = [1, 2, 3, 4, 3]
print(next_greater_elements_circular(nums))  # [2, 3, 4, -1, 4]

另一种写法（遍历 2n 次，统一入栈）：

def next_greater_elements_circular_v2(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []
    
    for i in range(2 * n - 1, -1, -1):
        # 从右往左遍历，维护单调递减栈
        actual = i % n
        while stack and stack[-1] <= nums[actual]:
            stack.pop()
        if stack and i < n:
            result[actual] = stack[-1]
        # 注意：这里存的是值而不是索引，因为环形数组中索引关系复杂
        stack.append(nums[actual])
    
    return result

2.5 单调栈在柱状图最大矩形中的完整推导

让我们严格推导 LeetCode #84 的解法。

问题形式化：给定 heights[0..n-1]，求 max(heights[k] * (right[k] - left[k] - 1))，其中：

• left[k] = 第 k 根柱子左边第一个高度 < heights[k] 的柱子索引（不存在则为 -1）
• right[k] = 第 k 根柱子右边第一个高度 < heights[k] 的柱子索引（不存在则为 n）

为什么以每根柱子为高就能覆盖最优解？

最优矩形的高度一定等于该矩形范围内最矮柱子的高度（否则可以降低高度但不增加宽度，面积不会更大）。所以最优矩形一定是"以某根柱子的高度为高，向两边扩展到不能扩展为止"。枚举所有柱子即可覆盖最优解。

两次遍历解法（概念更清晰）：

def largest_rectangle_two_pass(heights: list[int]) -> int:
    """
    分两次遍历分别求 left[] 和 right[]，
    再遍历一次计算最大面积。
    """
    n = len(heights)
    left = [-1] * n   # 左边第一个更矮的索引
    right = [n] * n   # 右边第一个更矮的索引
    
    # 从左到右，用单调递增栈求 left[]
    stack = []
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    # 从右到左，用单调递增栈求 right[]
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    # 计算最大面积
    max_area = 0
    for i in range(n):
        area = heights[i] * (right[i] - left[i] - 1)
        max_area = max(max_area, area)
    
    return max_area

一次遍历解法（用哨兵，更高效）：

核心观察：当我们从单调递增栈中弹出元素 k 时，正在入栈的元素 i 就是 right[k]，弹出后的新栈顶就是 left[k]。一次遍历就同时确定了左右边界！

这就是 Level 1 中那个带哨兵版本的原理。加哨兵的好处是省去了"栈为空"的判断和遍历结束后的额外清理。

2.6 单调栈的模板总结

经过上面的分析，我们可以提炼出单调栈的两大模板：

模板一：找右边第一个更大/更小元素

def find_right(nums, compare):
    """
    compare(a, b) 决定找什么：
    - compare = lambda a, b: a < b  → 找右边第一个更大的
    - compare = lambda a, b: a > b  → 找右边第一个更小的
    """
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(n):
        while stack and compare(nums[stack[-1]], nums[i]):
            result[stack.pop()] = i  # 或 nums[i]，视需求
        stack.append(i)
    return result

模板二：找左边第一个更大/更小元素

def find_left(nums, compare):
    """从左到右遍历，栈顶元素就是左边界"""
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(n):
        while stack and compare(nums[stack[-1]], nums[i]):
            stack.pop()
        result[i] = stack[-1] if stack else -1
        stack.append(i)
    return result

选择指南：

Level 3 · 规范怎么定义的

3.1 单调栈与分治的关系——笛卡尔树

**笛卡尔树（Cartesian Tree）**是由 Jean Vuillemin 在 1980 年的论文"A unifying look at data structures"（Communications of the ACM, 1980）中提出的一种二叉树，它同时满足：

1. BST 性质：中序遍历得到原始数组顺序
2. 堆性质：每个节点的值小于（或大于）其子节点

笛卡尔树与单调栈的惊人联系：

用单调栈对数组做一次线性扫描，得到的恰好就是这个数组的笛卡尔树！

def build_cartesian_tree(nums: list[int]):
    """
    用单调栈在 O(n) 时间内构建笛卡尔树（最小堆性质）。
    
    算法：
    1. 维护一个单调递增栈（值递增）。
    2. 新元素入栈时，弹出所有比它大的元素。
    3. 最后一个被弹出的元素成为新元素的左子树。
    4. 新元素成为当前栈顶的右子树。
    
    这与 Gabow, Bentley, and Tarjan (1984) 描述的线性时间
    笛卡尔树构造算法一致。
    """
    class Node:
        def __init__(self, val, idx):
            self.val = val
            self.idx = idx
            self.left = None
            self.right = None
    
    stack = []  # 存 Node
    
    for i, num in enumerate(nums):
        node = Node(num, i)
        last_popped = None
        
        while stack and stack[-1].val > num:
            last_popped = stack.pop()
        
        node.left = last_popped  # 最后弹出的成为左子树
        
        if stack:
            stack[-1].right = node  # 新节点成为栈顶的右子树
        
        stack.append(node)
    
    # 栈底元素是根
    return stack[0] if stack else None

笛卡尔树与柱状图最大矩形的关系：

柱状图最大矩形问题可以用分治法解决：

1. 找到区间 [l, r] 中的最小值 heights[m]
2. 以 m 为高的矩形面积 = heights[m] * (r - l + 1)
3. 递归解决 [l, m-1] 和 [m+1, r]

这个分治结构恰好对应 heights 数组的笛卡尔树！树的每个节点代表一次分治：节点值是区间最小值，左子树是左半段，右子树是右半段。

• 如果笛卡尔树平衡：分治深度 O(log n)，总时间 O(n log n)
• 如果笛卡尔树退化（如已排序数组）：深度 O(n)，总时间 O(n²)
• 而单调栈解法始终 O(n)，因为它不需要真的递归，而是在一次扫描中完成所有计算

总结：单调栈可以看作是"隐式构建笛卡尔树"的过程。分治在树上自顶向下，而单调栈在数组上从左到右，两者计算的是同一个东西，但单调栈避免了递归开销和最坏情况退化。

3.2 单调队列在 DP 优化中的应用

单调队列最深刻的应用不是滑动窗口最大值，而是优化动态规划的状态转移。当 DP 转移方程的形式为：

dp[i] = max/min { dp[j] + cost(j, i) }，其中 j 的范围是一个滑动窗口

时，单调队列可以将每个状态的计算从 O(k)（窗口大小）降到均摊 O(1)。

经典应用：多重背包优化

普通多重背包问题：有 N 种物品，第 i 种物品体积 vᵢ，价值 wᵢ，数量 sᵢ。背包容量 V，求最大价值。

朴素 DP：dp[j] = max(dp[j - kv] + kw)，k = 0, 1, ..., s，复杂度 O(NVS)。

单调队列优化：

对于固定的物品（体积 v，价值 w，数量 s），将所有容量 j 按照 j mod v 的余数分组。

在同一组中，设 j = r + p*v（r 是余数，p = 0, 1, 2, ...），则：

dp[r + pv] = max { dp[r + kv] - kw } + pw，其中 max(0, p-s) ≤ k ≤ p

这就是一个滑动窗口最大值问题！窗口大小为 s+1，我们对 dp[r + kv] - kw 维护单调队列。

def multiple_knapsack_deque(N: int, V: int, items: list[tuple]) -> int:
    """
    多重背包 - 单调队列优化
    items: [(volume, value, count), ...]
    
    时间复杂度：O(NV)，比朴素的 O(NVS) 显著优化
    空间复杂度：O(V)
    """
    dp = [0] * (V + 1)
    
    for vol, val, cnt in items:
        if vol == 0:
            continue
        # 按余数分组
        for r in range(vol):
            # 单调队列：存 (位置p, dp[r+p*vol] - p*val)
            dq = deque()
            # 遍历组内所有位置
            max_p = (V - r) // vol
            for p in range(max_p + 1):
                j = r + p * vol
                # 当前值：dp[j] - p * val
                cur_val = dp[j] - p * val
                
                # 维护单调递减队列
                while dq and dq[-1][1] <= cur_val:
                    dq.pop()
                dq.append((p, cur_val))
                
                # 移除超出窗口的队头
                if dq[0][0] < p - cnt:
                    dq.popleft()
                
                # 转移
                dp[j] = dq[0][1] + p * val
    
    return dp[V]

其他经典 DP 优化场景：

1. 最大子数组和（限长度）：求长度不超过 k 的最大子数组和。前缀和转化后变成：max(prefix[i] - prefix[j])，j ∈ [i-k, i-1]。对 prefix[j] 维护单调递增队列（找最小值）。

2. 跳跃游戏 VII（LeetCode #1871）：dp[i] = any(dp[j] for j in [i-maxJump, i-minJump])，可以用单调队列（或前缀和）优化。

3. Frog Jump II（USACO 问题）：dp[i] = min(dp[j]) + a[i]，j ∈ [i-k, i-1]，对 dp[j] 维护单调递增队列。

3.3 Amortized Analysis 证明单调栈是 O(n)

均摊分析有三种经典方法，均由 Robert Tarjan 在 1985 年的论文"Amortized Computational Complexity"（SIAM Journal on Algebraic and Discrete Methods）中系统化提出。让我们用三种方法证明单调栈的 O(n) 复杂度。

方法一：聚合分析（Aggregate Analysis）

不分析单次操作的代价，而是分析 n 次操作的总代价。

• push 操作总共执行 n 次（每个元素恰好入栈一次）
• pop 操作总共最多执行 n 次（每个元素最多出栈一次）
• 总代价 T(n) ≤ 2n
• 均摊代价 = T(n)/n = 2 = O(1)

方法二：记账法（Accounting Method / Banker's Method）

为每个操作设定一个"均摊代价"（可能高于或低于实际代价），只要"银行账户"永远非负即可。

• 给每次 push 操作设定均摊代价 = 2（实际代价 1，多付 1 存入"银行"）
• 给每次 pop 操作设定均摊代价 = 0（实际代价 1，从"银行"取 1 来支付）

验证：每个元素入栈时存了 1 块钱。当它出栈时，用这 1 块钱支付 pop 的代价。由于每个元素最多入栈一次、出栈一次，银行账户永远非负。

总均摊代价 = n × 2 = 2n = O(n)。

方法三：势能法（Potential Method / Physicist's Method）

定义势能函数 Φ(Dᵢ) = 栈在第 i 步操作后的元素个数。

初始势能 Φ(D₀) = 0，且 Φ(Dᵢ) ≥ 0（栈大小非负）。

对于第 i 步操作：

• 设弹出了 kᵢ 个元素（kᵢ ≥ 0），然后压入 1 个元素
• 实际代价：cᵢ = kᵢ + 1
• 势能变化：ΔΦᵢ = Φ(Dᵢ) - Φ(Dᵢ₋₁) = 1 - kᵢ
• 均摊代价：ĉᵢ = cᵢ + ΔΦᵢ = (kᵢ + 1) + (1 - kᵢ) = 2

不论 kᵢ 是多少，均摊代价恒为 2。

总代价 = Σcᵢ = Σĉᵢ - (Φ(Dₙ) - Φ(D₀)) ≤ 2n - 0 = 2n = O(n)。

为什么三种方法结果一致？

因为它们分析的是同一个事实的不同表述。聚合分析直接数总量；记账法把代价预支到"便宜"的操作上；势能法把"暂存的工作"编码为势能。本质上都是在说：pop 的总次数受限于 push 的总次数。

3.4 单调栈的历史背景与理论地位

单调栈作为一种算法技巧，最早的系统化应用可以追溯到以下工作：

1. Histogram 最大矩形问题：最早的线性时间解法出现在 "A Linear Time Algorithm for Computing the Area of the Largest Rectangle in a Histogram"（Žilvinas, 1992），但实际上用栈解决此问题的想法更早，可追溯到 1980 年代的计算几何文献。

2. All Nearest Smaller Values 问题：Berkman, Schieber, and Vishkin (1993) 在 "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values" 中将"找所有最近更小值"形式化为一个标准问题，并给出了并行算法。串行版本就是单调栈。

3. 笛卡尔树的构造：Vuillemin (1980) 和 Gabow, Bentley, Tarjan (1984) 的工作奠定了单调栈与笛卡尔树之间的联系。

在竞赛编程（Competitive Programming）领域，单调栈/单调队列是从 1990 年代 IOI/ACM 竞赛中发展出来的标准技巧，后来被 LeetCode 等平台带入面试领域。

Level 4 · 边界与陷阱

4.1 接雨水的四种解法完整对比

LeetCode #42 — Trapping Rain Water 是面试中考察频率最高的题目之一。它有至少四种不同思路的解法，每种都体现了不同的算法思维。

解法一：暴力（O(n²) 时间，O(1) 空间）

def trap_brute(height: list[int]) -> int:
    """
    对每个位置 i，分别找：
    - left_max：i 左边（含 i）的最高柱子
    - right_max：i 右边（含 i）的最高柱子
    位置 i 能存的水 = min(left_max, right_max) - height[i]
    
    正确性证明：位置 i 的水位由左右最高柱子中较矮的那个决定（木桶原理）。
    """
    n = len(height)
    water = 0
    for i in range(n):
        left_max = max(height[:i + 1])
        right_max = max(height[i:])
        water += min(left_max, right_max) - height[i]
    return water

解法二：前缀最大值（O(n) 时间，O(n) 空间）

def trap_prefix(height: list[int]) -> int:
    """
    预计算每个位置的 left_max[] 和 right_max[]，避免重复计算。
    """
    n = len(height)
    if n == 0:
        return 0
    
    left_max = [0] * n
    right_max = [0] * n
    
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])
    
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

解法三：单调栈（O(n) 时间，O(n) 空间）

（已在 Level 1 展示，按行计算水量）

解法四：双指针（O(n) 时间，O(1) 空间）

def trap_two_pointers(height: list[int]) -> int:
    """
    双指针是前缀最大值法的空间优化版本。
    
    核心洞察：
    - 如果 left_max < right_max，那么位置 left 的水量只取决于 left_max
      （因为右边一定有个更高的柱子兜底）
    - 反之亦然
    
    所以我们不需要预计算两个数组，只需要两个指针从两端向中间移动，
    每次移动"短板"那一侧。
    """
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    
    while left < right:
        if height[left] < height[right]:
            # 右边存在一个 >= height[right] > height[left] 的柱子
            # 所以 left 位置的水量取决于 left_max
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    
    return water

四种解法对比：

面试建议：先说暴力思路O(n²)，然后优化到前缀最大值O(n)/O(n)，最后给出双指针O(n)/O(1)。如果面试官问单调栈版本再补充。展示"逐步优化"的思考过程比直接给最优解更有说服力。

4.2 股票价格跨度（LeetCode #901）

问题：设计一个类 StockSpanner，每天收到一个股票价格，返回当天及之前连续多少天价格 ≤ 今天的。

示例：prices = [100, 80, 60, 70, 60, 75, 85]，输出 = [1, 1, 1, 2, 1, 4, 6]

这道题本质是"找左边第一个比当前元素大的元素"——即从当前位置往左看，连续比自己小的有多少个。

class StockSpanner:
    """
    股票价格跨度 - 单调递减栈
    
    维护一个从栈底到栈顶价格严格递减的栈。
    栈中存 (price, span)，span 表示这个价格"吞掉"了多少天。
    
    当新价格 >= 栈顶价格时，栈顶被弹出，其 span 累加到新价格的 span 中。
    
    时间复杂度：均摊 O(1) 每次调用（总共 O(n)）
    空间复杂度：O(n)
    """
    
    def __init__(self):
        self.stack = []  # (price, span)
    
    def next(self, price: int) -> int:
        span = 1  # 至少包含今天自己
        
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack[-1][1]
            self.stack.pop()
        
        self.stack.append((price, span))
        return span


# 测试
spanner = StockSpanner()
prices = [100, 80, 60, 70, 60, 75, 85]
for p in prices:
    print(spanner.next(p), end=' ')  # 1 1 1 2 1 4 6
print()

这道题的巧妙之处：栈里存的不是单纯的索引或值，而是 (价格, 跨度) 对。当一个价格被弹出时，它的"跨度"被合并到新元素中。这相当于新元素"吞噬"了所有比它矮的历史记录。

常见错误：

• 用 < 而不是 <=：题目说的是"小于等于当天的连续天数"，所以相等也要弹出
• 忘记算上自己（span 初始化为 1 而不是 0）

4.3 最大矩形（LeetCode #85 基于 #84）

问题：给定一个仅包含 0 和 1 的二维矩阵，找出只包含 1 的最大矩形面积。

关键洞察：将每一行看作"地基"，向上统计连续 1 的个数作为柱子高度，就把二维问题转化为多次一维柱状图最大矩形问题。

def maximal_rectangle(matrix: list[list[str]]) -> int:
    """
    最大矩形 - 基于 LeetCode #84 的柱状图最大矩形
    
    思路：
    1. 逐行构建"直方图"：heights[j] = 该列从当前行往上连续 1 的个数
    2. 对每行的直方图调用 largest_rectangle_area
    
    时间复杂度：O(m * n)，m 行 n 列
    空间复杂度：O(n)
    """
    if not matrix or not matrix[0]:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    heights = [0] * n
    max_area = 0
    
    for i in range(m):
        # 更新直方图
        for j in range(n):
            if matrix[i][j] == '1':
                heights[j] += 1
            else:
                heights[j] = 0  # 遇到 0，柱子断裂
        
        # 对当前行的直方图求最大矩形
        max_area = max(max_area, largest_rectangle_area(heights))
    
    return max_area


def largest_rectangle_area(heights: list[int]) -> int:
    """同 Level 1 的实现"""
    heights_ext = [0] + heights + [0]
    stack = [0]
    max_area = 0
    
    for i in range(1, len(heights_ext)):
        while heights_ext[i] < heights_ext[stack[-1]]:
            h = heights_ext[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, h * width)
        stack.append(i)
    
    return max_area


# 测试
matrix = [
    ['1', '0', '1', '0', '0'],
    ['1', '0', '1', '1', '1'],
    ['1', '1', '1', '1', '1'],
    ['1', '0', '0', '1', '0']
]
print(maximal_rectangle(matrix))  # 6

逐行直方图变化过程：

行 0: heights = [1, 0, 1, 0, 0] → 最大矩形 = 1
行 1: heights = [2, 0, 2, 1, 1] → 最大矩形 = 3
行 2: heights = [3, 1, 3, 2, 2] → 最大矩形 = 6  ← 全局最大
行 3: heights = [4, 0, 0, 3, 0] → 最大矩形 = 4

第 2 行中，heights = [3, 1, 3, 2, 2]，以高度 2 为高可以覆盖索引 2-4，面积 = 2*3 = 6。

4.4 严格单调 vs 非严格单调

这是单调栈最容易出错的地方。< 和 <= 的一字之差，会导致完全不同的行为。

场景分析：

以"下一个更大元素"为例，数组 [5, 5, 5, 3]：

1. 严格单调递减栈（弹出条件 stack[-1] < nums[i]）：

   • 相等元素不弹出，都留在栈里
   • 三个 5 都在栈里，它们的"下一个更大"都是 -1
   • 正确！因为确实没有"更大的"

2. 非严格单调递减栈（弹出条件 stack[-1] <= nums[i]）：

   • 相等元素也弹出
   • 第一个 5 遇到第二个 5 时被弹出，result[0] = 5
   • 错误！5 不比 5 大

规则：

• 找"严格更大/更小"：用 < / > 作为弹出条件
• 找"大于等于/小于等于"：用 <= / >= 作为弹出条件

在柱状图最大矩形中的特殊情况：

heights = [2, 2, 2]，正确答案是 6（三根柱子组成 2×3 的矩形）。

如果用严格单调（heights[stack[-1]] > heights[i] 才弹出）：

• 三个 2 相等，不弹出，栈 = [0, 1, 2]
• 最后被右哨兵弹出时：
  • 弹出 2：width = 3 - 1 - 1 = 1，area = 2
  • 弹出 1：width = 3 - 0 - 1 = 2，area = 4
  • 弹出 0：width = 3 - (-1) - 1 = 3，area = 6 ✓

如果用非严格单调（heights[stack[-1]] >= heights[i] 才弹出）：

• 第二个 2 弹出第一个：width = 1 - ? 这取决于栈是否为空
• 处理更复杂，但最终结果也可以正确

结论：在柱状图问题中，两种写法都能得到正确结果，但推理过程不同。建议用 >= 弹出（非严格）+ 哨兵，这是最安全的写法。

4.5 什么时候用单调栈 vs 优先队列（堆）

两者都能找"最大/最小"，但适用场景截然不同：

判断标准：

1. 问题是否有"顺序性"？ 如果是逐个处理数组元素，找某个方向上的第一个满足条件的 → 单调栈
2. 是否需要全局最值？ 如果需要在任意时刻知道所有数据中的最大/最小值 → 堆
3. 是否有滑动窗口？ 如果窗口固定大小且只需最值 → 单调队列（O(n)）优于堆（O(n log n)）
4. 是否需要第 K 大？ → 堆（单调栈/队列做不了 Top-K）

混合使用的场景：

有些题目需要结合两者。例如"数据流中的中位数"（LeetCode #295）用两个堆，但如果加上"滑动窗口内的中位数"（LeetCode #480），则需要更复杂的数据结构（多重集合或可删除堆）。

4.6 面试实战策略

单调栈题目的识别特征：

1. 题目问"下一个更大/更小"或"前一个更大/更小"
2. 题目涉及"左右边界"（如柱状图、接雨水）
3. 题目可以转化为"对每个元素找某个方向上第一个满足条件的"
4. 看到 O(n²) 暴力解中有"对每个元素向一个方向扫描"的模式

面试中的表达模板：

"这道题暴力解法是对每个元素向右扫描找第一个更大值，O(n²)。但我们观察到：如果元素 A 右边有元素 B > A，那么 B 也能'帮助'到 A 左边那些比 B 小的元素。利用这个传递性，我们可以用单调栈——维护一个递减的栈，新元素入栈时弹出所有比它小的，被弹出的就找到了答案。每个元素入栈出栈各一次，总复杂度 O(n)。"

高频面试题清单：

4.7 补充题目：子数组最小值之和（LeetCode #907）

这道题展示了单调栈的一个重要应用模式——贡献法。

问题：给定数组 arr，求所有子数组的最小值之和，结果对 10⁹+7 取模。

暴力：枚举所有 O(n²) 个子数组，每个找最小值，O(n³) 或 O(n²)。

单调栈 + 贡献法：对每个元素 arr[i]，计算它作为最小值出现在多少个子数组中。

如果 arr[i] 是 [left, right] 范围内的最小值，那么包含 i 且完全在 [left, right] 内的子数组数量 = (i - left) * (right - i)。

def sum_subarray_mins(arr: list[int]) -> int:
    """
    子数组最小值之和 - 单调栈 + 贡献法
    
    对每个 arr[i]，找到：
    - left[i]：左边第一个严格更小的元素的索引（处理相等时用 <）
    - right[i]：右边第一个小于等于的元素的索引（处理相等时用 <=）
    
    注意 left 和 right 对相等元素的处理不同！
    这是为了避免重复计算：对于相等元素，我们规定"左边用严格，右边用非严格"
    （或反过来），确保每个子数组的最小值只被一个位置"负责"。
    
    arr[i] 作为最小值的子数组个数 = (i - left[i]) * (right[i] - i)
    贡献 = arr[i] * (i - left[i]) * (right[i] - i)
    """
    MOD = 10**9 + 7
    n = len(arr)
    
    # left[i]: 左边第一个严格更小的索引，不存在为 -1
    left = [-1] * n
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:  # >= 表示相等也弹出
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    # right[i]: 右边第一个小于等于的索引，不存在为 n
    right = [n] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:  # > 表示相等不弹出
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    # 计算总贡献
    result = 0
    for i in range(n):
        result += arr[i] * (i - left[i]) * (right[i] - i)
        result %= MOD
    
    return result


# 测试
arr = [3, 1, 2, 4]
print(sum_subarray_mins(arr))  # 17
# 子数组: [3]=3, [1]=1, [2]=2, [4]=4, [3,1]=1, [1,2]=1, [2,4]=2, [3,1,2]=1, [1,2,4]=1, [3,1,2,4]=1
# 和 = 3+1+2+4+1+1+2+1+1+1 = 17

为什么左右对相等元素的处理不同？

考虑 arr = [1, 1, 1]。子数组 [1,1,1] 的最小值是 1，这个贡献应该只算一次。如果左右都用严格 <，三个位置都会"声称"自己负责这个子数组，导致重复计算。

解决方案：规定一个"归属规则"。比如"相等时归属于最左边那个"：

• left 用 >=（相等也弹出，即寻找严格更小的边界）
• right 用 >（相等不弹出，即寻找小于等于的边界）

这样，对于连续相等的元素，只有最左边的那个拥有最大的"负责范围"。

4.8 总结与直觉建图

                    单调栈/单调队列知识图谱
                    
    ┌─────────────────────────────────────────────┐
    │               应用问题                        │
    │  ┌──────┐  ┌──────┐  ┌──────┐  ┌──────┐    │
    │  │NGE   │  │接雨水│  │最大矩│  │滑动窗│    │
    │  │#496  │  │#42   │  │形#84 │  │口#239│    │
    │  └──┬───┘  └──┬───┘  └──┬───┘  └──┬───┘    │
    └─────┼─────────┼─────────┼─────────┼────────┘
          │         │         │         │
          v         v         v         v
    ┌─────────────────────────────────────────────┐
    │            核心数据结构                       │
    │                                              │
    │   单调递减栈        单调递增栈     单调队列    │
    │   (找更大)          (找更小)       (窗口最值) │
    └──────────────────────┬──────────────────────┘
                           │
                           v
    ┌─────────────────────────────────────────────┐
    │            底层原理                           │
    │                                              │
    │  均摊 O(n)     笛卡尔树      DP 优化         │
    │  (势能法)      (分治等价)    (多重背包)       │
    └─────────────────────────────────────────────┘

记忆口诀：

单调栈，找邻居——左右第一个更大/更小的那个。 单调队列，看窗口——滑动窗口里谁最大/最小。 入栈出栈各一次，均摊线性不犹豫。 哨兵一加边界消，严格非严别搞混。

本章练习

基础题（Level 1-2）

1. 实现 LeetCode #496，使用单调栈 + 哈希表。
2. 实现 LeetCode #739，统计每日温度的等待天数。
3. 实现 LeetCode #239，使用单调队列。
4. 对比 #42 的前缀最大值和双指针解法，手动模拟 [4,2,0,3,2,5]。

进阶题（Level 3-4）

5. 实现 LeetCode #84 的两种写法（两次遍历 vs 哨兵一次遍历），对比。
6. 实现 LeetCode #85，基于 #84。
7. 实现 LeetCode #907，注意处理相等元素。
8. 用势能法证明：如果允许每个元素入栈最多 2 次（如环形数组遍历两遍），总复杂度是 O(n) 还是 O(2n)？

思考题

9. 为什么双指针做接雨水不需要栈？它的正确性来自哪个数学性质？
10. 如果面试官要求 O(1) 空间解决 #84（柱状图最大矩形），可能吗？为什么？