单调栈原理

单调栈和普通栈的区别是什么？

• 单调递增栈: 只有比栈顶小的元素可以直接进栈, 否则先弹出所有比当前元素小的元素再进栈;
• 单调递减栈: 只有比栈顶大的元素可以直接进栈, 否则先弹出所有比当前元素大的元素再进栈;
• 结果: 栈内元素自底向顶保持单调, 弹出的元素恰好是"被当前元素终结"的候选;

def monotoneIncreasingStack(nums):
    stack = []
    for num in nums:
        while stack and num >= stack[-1]:
            stack.pop()
        stack.append(num)

def monotoneDecreasingStack(nums):
    stack = []
    for num in nums:
        while stack and num <= stack[-1]:
            stack.pop()
        stack.append(num)

单调栈能回答哪四类问题？

问题是"寻找左/右侧第一个比当前元素大/小的元素":

目标	栈类型	答案位置
左侧第一个更大	单调递增栈	插入当前元素时的栈顶
左侧第一个更小	单调递减栈	插入当前元素时的栈顶
右侧第一个更大	单调递增栈	当前元素弹出时的"插入者"
右侧第一个更小	单调递减栈	当前元素弹出时的"插入者"

• 口诀: 从左向右遍历; 找更大用递增栈, 找更小用递减栈; 左侧看插入时的栈顶, 右侧看弹栈时的插入者;
• 不存在的情况: 栈为空 (左侧) 或从未被弹出 (右侧) 说明答案不存在;

等于号该不该写进判断条件？

• 求左侧第一个更大/更小: 判断里带等号 (num >= stack[-1]), 让相等元素也弹出;
• 求右侧第一个更大/更小: 判断里不带等号, 相等元素留在栈里继续等待;
• 理由: 等号决定的是"相等元素算不算能满足条件", 左右两侧的语义相反;

单调栈为什么整体是 O(n)？

• 关键: 每个元素在遍历中最多进栈一次、出栈一次;
• 所以内层 while 的总弹出次数不超过 $n$, 总时间 $O(n)$;
• 常见用法: 栈里存元素值 (求下一个更大元素) 或存下标 (求距离、求区间宽度);