单调栈

What · 是什么

单调栈(Monotonic Stack)是在栈的基础上维护元素单调性(递增或递减)的数据结构。在元素入栈时，弹出所有破坏单调性的栈顶元素，使得栈内元素始终保持有序。可在 O(n) 时间内对每个元素找到其左侧/右侧第一个大于/小于它的元素。

Why · 为什么

How · 实现

伪代码

# 求每个元素右侧第一个更大的元素位置
# 维护单调递减栈(栈存下标)
for i in range(n):
  while not st.empty() and a[st.top()] < a[i]:
    ans[st.pop()] = i  # i 是 st.top() 右侧第一个更大的位置
  st.push(i)
# 栈中剩余元素的 ans 为 -1(无更大元素)

Python 实现

def daily_temperatures(temps):
    """LeetCode 739: 每日温度
    对每天, 求下一个更暖和的日子在几天后。
    单调递减栈(存下标), 弹出时记录距离。
    """
    n = len(temps)
    ans = [0] * n
    st = []  # 栈存下标, 维护对应的温度递减
    for i in range(n):
        while st and temps[st[-1]] < temps[i]:
            j = st.pop()
            ans[j] = i - j  # 距离 = 天数差
        st.append(i)
    return ans


def next_greater_element(nums):
    """求每个元素右侧第一个更大的元素值(不存在则-1)。
    单调递减栈。
    """
    n = len(nums)
    ans = [-1] * n
    st = []
    for i in range(n):
        while st and nums[st[-1]] < nums[i]:
            ans[st.pop()] = nums[i]
        st.append(i)
    return ans


def left_right_smaller(n, arr):
    """对每个元素, 求左侧第一个<它 和 右侧第一个<它 的下标。
    左侧: 从左到右维护递增栈; 右侧: 从右到左维护递增栈。
    """
    left = [-1] * n
    st = []
    for i in range(n):
        while st and arr[st[-1]] >= arr[i]:
            st.pop()
        if st:
            left[i] = st[-1]
        st.append(i)

    right = [-1] * n
    st = []
    for i in range(n - 1, -1, -1):
        while st and arr[st[-1]] >= arr[i]:
            st.pop()
        if st:
            right[i] = st[-1]
        st.append(i)

    return left, right


if __name__ == '__main__':
    # 测试每日温度
    temps = [73, 74, 75, 71, 69, 72, 76, 73]
    result = daily_temperatures(temps)
    print(f'Daily temperatures: {result}')
    assert result == [1, 1, 4, 2, 1, 1, 0, 0]

    # 测试下一个更大元素
    nums = [2, 1, 2, 4, 3]
    nge = next_greater_element(nums)
    print(f'Next greater: {nge}')
    assert nge == [4, 2, 4, -1, -1]

    # 测试左右更小
    arr = [3, 1, 4, 1, 5, 9, 2, 6]
    left, right = left_right_smaller(len(arr), arr)
    print(f'Left smaller:  {left}')
    print(f'Right smaller: {right}')

    print('All monotonic stack tests passed!')

易错点

• 栈中存值还是存下标: 需要答案位置时必须存下标，存值会丢失位置信息
• 递增还是递减搞反: 求下一个更大→递减栈(弹出比当前小的); 求下一个更小→递增栈
• 弹出条件用 <= 还是 <: 含等号时相等的元素也弹出(适用于'严格更大')，不含等号则保留(适用于'非严格更大')
• 忘记处理栈中剩余元素(它们的答案为 -1/0 表示无更大元素)

例题

信源

• OI Wiki✓ https://oi-wiki.org/ds/monotonic-stack/
• CP-Algorithms✓ https://cp-algorithms.com/data_structures/stack_queue_modification.html