算法技巧：单调栈

hweiyu00

782人浏览 · 2026-01-21 10:54:09

hweiyu00 · 2026-01-21 10:54:09 发布

单调栈完整详解

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、单调栈是什么

单调栈是一种具有单调性的栈结构，是栈的一个重要变种，核心特征是：栈内的所有元素，始终严格遵守「递增」或「递减」的顺序排列，新元素入栈时会触发特殊的弹出规则，保证这种单调性不被破坏。
核心价值：单调栈可以做到 在 O(n) 线性时间复杂度 内，高效解决数组中「每个元素找左右侧第一个更大/更小元素」的一类经典问题，这类问题暴力解的时间复杂度为 O(n²)，单调栈是该类问题的最优解。
补充说明：单调栈本质是「空间换时间」，空间复杂度为 O(n)，用栈的存储空间，把原本需要两层循环的暴力解，优化为一次遍历即可完成。

二、单调栈的核心特性

核心定义

栈内元素满足严格的单调性，只有两种核心类型，无其他变种：

单调递增栈：栈内的元素，从栈底到栈顶依次严格增大 → 栈顶是当前栈内的最大值
单调递减栈：栈内的元素，从栈底到栈顶依次严格减小 → 栈顶是当前栈内的最小值

核心入栈规则核心重点

这是单调栈的灵魂，所有操作都基于这个规则，新元素入栈必触发该规则，规则统一：
当准备将新元素 num 入栈时，循环判断「栈顶元素」与「新元素 num」的大小关系：

如果栈顶元素不满足当前栈的单调性要求 → 将栈顶元素弹出栈
重复弹出操作，直到栈为空或栈顶元素满足单调性要求
最后将新元素 num 压入栈中

两个核心结论必记

所有元素只会入栈一次、出栈一次，不会重复入栈和出栈，这是单调栈能做到 O(n) 时间复杂度的核心原因。
单调栈解决的问题具有极强的专一性：专门解决数组中元素的「左右侧第一个最值匹配」问题，遇到这类问题，无脑用单调栈即可。

三、单调栈的核心应用场景两类核心问题

单调栈的应用场景高度固定，笔试面试中99%的考题都围绕这两个场景展开，记住「场景对应栈类型」的规则，解题效率翻倍，无任何例外：

场景一找数组中每个元素「右侧第一个更大的元素」

✅ 对应栈类型：单调递减栈

场景二找数组中每个元素「右侧第一个更小的元素」

✅ 对应栈类型：单调递增栈

衍生场景均为上述两类的变形规则不变

找每个元素「左侧第一个更大的元素」
找每个元素「左侧第一个更小的元素」
找每个元素「左右侧第一个更大元素的距离」
找每个元素「左右侧第一个更小元素的距离」

核心规律：「左侧」类问题，从数组左到右遍历；「右侧」类问题，从数组右到左遍历。

四、核心场景实战含完整可运行代码

所有案例均为 Python 实现，代码为最优解写法，无冗余逻辑，可直接套用，所有案例统一使用测试数组：nums = [2, 1, 2, 4, 3]

前置说明

栈中存储的是数组的「下标」而非元素值，这是单调栈的标准写法、最优写法，原因有2点：

既可以通过下标获取元素值，也能获取元素的位置信息；
求解「元素距离」类问题时，必须用到下标计算，存储值无法实现。

实战1 找每个元素右侧第一个更大的元素

问题描述：遍历数组，对每个元素，返回其右侧第一个比它大的元素，无则返回 -1
测试数组：[2,1,2,4,3] → 正确结果：[4,2,4,-1,-1]
对应栈类型：单调递减栈
遍历顺序：从右向左遍历

def next_greater_element(nums):
    n = len(nums)
    res = [-1] * n  # 初始化结果数组，默认值-1
    stack = []      # 单调递减栈，存下标
    # 从右向左遍历
    for i in range(n-1, -1, -1):
        # 核心规则：栈顶元素对应的值 <= 当前值，弹出栈顶，破坏单调性则弹出
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()
        # 栈不为空，栈顶就是右侧第一个更大的元素的下标
        if stack:
            res[i] = nums[stack[-1]]
        # 入栈当前下标
        stack.append(i)
    return res

nums = [2,1,2,4,3]
print(next_greater_element(nums))  # 输出 [4, 2, 4, -1, -1]

实战2 找每个元素右侧第一个更小的元素

问题描述：遍历数组，对每个元素，返回其右侧第一个比它小的元素，无则返回 -1
测试数组：[2,1,2,4,3] → 正确结果：[1,-1,-1,3,-1]
对应栈类型：单调递增栈
遍历顺序：从右向左遍历

def next_smaller_element(nums):
    n = len(nums)
    res = [-1] * n
    stack = []  # 单调递增栈，存下标
    for i in range(n-1, -1, -1):
        # 核心规则：栈顶元素对应的值 >= 当前值，弹出栈顶
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        if stack:
            res[i] = nums[stack[-1]]
        stack.append(i)
    return res

nums = [2,1,2,4,3]
print(next_smaller_element(nums))  # 输出 [1, -1, -1, 3, -1]

实战3 找每个元素左侧第一个更大的元素

问题描述：遍历数组，对每个元素，返回其左侧第一个比它大的元素，无则返回 -1
测试数组：[2,1,2,4,3] → 正确结果：[-1,2,-1,-1,4]
对应栈类型：单调递减栈
遍历顺序：从左向右遍历

def prev_greater_element(nums):
    n = len(nums)
    res = [-1] * n
    stack = []  # 单调递减栈，存下标
    # 从左向右遍历
    for i in range(n):
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()
        if stack:
            res[i] = nums[stack[-1]]
        stack.append(i)
    return res

nums = [2,1,2,4,3]
print(prev_greater_element(nums))  # 输出 [-1, 2, -1, -1, 4]

实战4 找每个元素左侧第一个更小的元素

问题描述：遍历数组，对每个元素，返回其左侧第一个比它小的元素，无则返回 -1
测试数组：[2,1,2,4,3] → 正确结果：[-1,-1,1,2,2]
对应栈类型：单调递增栈
遍历顺序：从左向右遍历

def prev_smaller_element(nums):
    n = len(nums)
    res = [-1] * n
    stack = []  # 单调递增栈，存下标
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        if stack:
            res[i] = nums[stack[-1]]
        stack.append(i)
    return res

nums = [2,1,2,4,3]
print(prev_smaller_element(nums))  # 输出 [-1, -1, 1, 2, 2]

五、单调栈经典高频面试题接雨水柱状图中最大的矩形

这两道题是单调栈的天花板级经典考题，笔试面试必考，本质都是「左右侧第一个最值」问题的组合应用，掌握后即可吃透单调栈的所有考点，两道题均为困难级但有固定解题模板。

经典题1 接雨水

问题描述：给定一个非负整数数组表示柱子高度，数组元素围成的容器能接多少雨水
核心思路：对每个柱子，能接的雨水量 = 「左侧第一个更高柱子高度」和「右侧第一个更高柱子高度」的最小值 - 当前柱子高度，累加所有柱子的接水量即可。
对应栈类型：单调递减栈

def trap(height):
    res = 0
    stack = []  # 单调递减栈，存下标
    n = len(height)
    for i in range(n):
        # 栈顶高度 < 当前高度，形成凹槽，可接水
        while stack and height[stack[-1]] < height[i]:
            cur = stack.pop()  # 凹槽底部的柱子下标
            if not stack:
                break
            left = stack[-1]   # 左侧第一个更高的柱子
            width = i - left - 1
            high = min(height[left], height[i]) - height[cur]
            res += width * high
        stack.append(i)
    return res

height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height))  # 输出 6

经典题2 柱状图中最大的矩形

问题描述：给定非负整数数组表示柱状图高度，每个柱子宽度为1，求柱状图中能勾勒出的最大矩形面积
核心思路：对每个柱子，能构成的最大矩形宽度 = 「右侧第一个更矮柱子下标」 - 「左侧第一个更矮柱子下标」 - 1，面积 = 宽度 × 当前高度，取所有面积的最大值即可。
对应栈类型：单调递增栈

def largest_rectangle_area(heights):
    # 数组首尾补0，简化边界处理
    heights = [0] + heights + [0]
    stack = []
    max_area = 0
    for i in range(len(heights)):
        # 栈顶高度 > 当前高度，计算栈顶柱子的最大面积
        while stack and heights[stack[-1]] > heights[i]:
            cur = stack.pop()
            # 栈顶弹出后的新栈顶，就是左侧第一个更矮的柱子
            width = i - stack[-1] - 1
            area = heights[cur] * width
            max_area = max(max_area, area)
        stack.append(i)
    return max_area

heights = [2,1,5,6,2,3]
print(largest_rectangle_area(heights))  # 输出 10