企业官网建设流程全解析

单调栈（Monotonic Stack）本质上就是**“带约束的栈”：
在任何时刻，栈内元素都保持单调递增或单调递减**的顺序。一旦新元素破坏这个单调性，就不断出栈，直到恢复单调为止。

一、为什么要有单调栈？

很多问题的核心是这类需求：

• 对每个元素，快速找到它左边/右边第一个比它大或小的元素

• 比如：

  • 下一个更大元素（Next Greater Element）
  • 柱状图最大矩形
  • 接雨水
  • 股票价格跨度

如果暴力做：
每个元素向左/右扫描，时间复杂度是O(n²)

单调栈的价值在于：
把这类问题统一降到 O(n)

二、单调栈的核心不变量（Invariant）

单调栈始终维护一个顺序不被破坏的栈结构：

• 单调递增栈：栈底 → 栈顶，值越来越大
• 单调递减栈：栈底 → 栈顶，值越来越小

关键不是“递增/递减”本身，而是：

栈里留下的，都是“还没找到答案”的元素

一旦某个新元素能“解决”栈顶元素的问题，
栈顶就该出栈了。

三、为什么是 O(n)？

这是单调栈最容易被误解、但最重要的一点。

每个元素：

• 最多入栈一次
• 最多出栈一次

所以：

• 总入栈 ≤ n
• 总出栈 ≤ n
• 总操作 ≤ 2n →O(n)

哪怕有while循环，也不会爆。

四、栈里到底存什么？

这点非常关键，很多人会混淆。

两种常见存法

1. 存「值」

• 适合只关心大小关系
• 比如 Next Greater Element（只要值）

2. 存「下标」（更常见）

• 需要算距离、区间、面积时必须用下标

• 比如：

  • 柱状图最大矩形
  • 接雨水
  • 最近更大/更小元素的距离

实战中90% 都是存下标

五、四种经典变体（一定要会的表）

一句口诀：

找「更大」用递减栈，找「更小」用递增栈

六、单调栈的本质理解（很重要）

你可以把单调栈理解为：

一种“延迟决策”的结构

• 元素入栈：
  “我还不知道我的答案是谁”
• 元素出栈：
  “答案找到了，不需要我了”

栈中始终保存的是：

• 未来可能被某个元素解决的问题集合

八、什么时候你该想到单调栈？

看到这些关键词，条件反射就对了：

• 「第一个 / 最近的」
• 「左边 / 右边」
• 「比它大 / 比它小」
• 「区间 / 连续 / 最大 / 最小」

好，这里给你一组单调栈必刷经典题清单，我会按「题目 → 思路 → 单调栈过程 → 答案实现」完整走一遍。
从入门 → 核心 → 进阶，基本覆盖 90% 面试/竞赛场景。

九、经典题目

1、下一个更大元素（单调栈入门）

题目

给定数组nums，返回一个数组res，
res[i]是nums[i]右边第一个比它大的元素，没有则为-1。

输入: [2,1,2,4,3] 输出: [4,2,4,-1,-1]

思路

• 从左到右扫描
• 用单调递减栈
• 栈中保存「还没找到更大元素的下标」

单调栈过程

nums = [2,1,2,4,3] i=0: stack=[0] i=1: stack=[0,1] i=2: nums[2]=2 > nums[1]=1 → pop 1 → res[1]=2 stack=[0,2] i=3: 4 > 2 → pop 2 → res[2]=4 4 > 2 → pop 0 → res[0]=4 stack=[3] i=4: stack=[3,4]

答案（Python）

defnext_greater(nums):n=len(nums)res=[