单调栈思想：局部最值、边界扩张与贡献统计

Set 可以帮我们把数字排好序，但如果问题问的是“右边第一个比我大的数在哪里”，还能先排序吗？

不行，排序后位置关系就丢了。我们得留在原序列里找答案。

最直接的办法，是每个位置都往右扫一遍，最坏要 $O(n^2)$ 。这节课试着换个方向：不让每个人自己找答案，而让新来的数给前面的人发答案。

一、单调栈 (Monotonic Stack) 核心定义

单调栈本质上是一个标准栈（Stack），但其压入元素的规则受到严格限制：每次新元素入栈前，必须将栈顶所有“破坏单调性”的元素弹出，从而让栈内元素自底向上保持单调。相等的数留不留，取决于题目要找“严格更大”还是“大于等于”。

在面对“寻找距离当前位置最近的极值点”这类问题时，如果我们针对每个元素向左或向右依次遍历，时间复杂度是 $O(N^2)$ 。单调栈通过在压栈时的“剔除”操作，保证栈顶始终是距离当前元素最近的有效候选人。

通俗理解： “排队等答案”。栈里暂时没找到右侧更大数的位置，先排着队。新数来了，比栈顶大？那栈顶要等的人就是它，记下答案后出栈。处理完后，新数也加入队伍，等自己的答案。

二、核心原理推导 (State Transition & Query)

1. 状态定义

设 st 为 std::stack<int> 类型的栈。和下一讲的单调队列一样，栈中极其建议存储原数组 $a$ 的下标 $i$ ，而不是具体的元素值 $a[i]$ 。

存储下标既能方便计算跨度（如宽度、距离），又能随时通过 a[st.top()] $O(1)$ 获取元素真实值。在执行任何栈顶读取或弹出操作前，必须通过 !st.empty() 确保栈非空。

2. 出栈规则 (寻找边界)

当遍历到新元素 $a[i]$ 时，开始将其与栈顶元素 $a[st.top()]$ 比较。

例如求右侧首个更大元素（维护单调递减栈）：如果发现当前元素 $a[i] > a[st.top()]$ ，这说明对于栈顶元素而言，它苦苦寻找的“右侧首个比它大的元素”终于出现了，正是 $a[i]$ ！此时不仅可以记录栈顶元素的答案，而且该栈顶元素的答案已经确定，不用继续等了，执行 st.pop() 将其弹出。循环此过程，直到栈顶元素大于等于 $a[i]$ 或栈为空。

3. 入栈规则 (延续传递)

当所有破坏单调性且找到了归宿的栈顶元素均被弹出后，当前元素下标 $i$ 将被压入栈中 st.push(i)，等待它自己的“右侧首个更大元素”在未来出现。因为每个元素最多只会入栈一次、出栈一次，所以整体算法均摊时间复杂度为严格的 $O(N)$ 。

4. 拿五个数走一遍

取 a=[5,3,3,4,6]，下标从 1 开始。栈里写成“下标:值”：

新来的位置	发生了什么	处理后的栈（底→顶）
1，值 5	暂时没有答案，入栈	`1:5`
2，值 3	3 比 5 小，继续等	`1:5, 2:3`
3，值 3	相等不算更大，两个 3 都留下	`1:5, 2:3, 3:3`
4，值 4	依次给位置 3、2 发下标 4（值 4）	`1:5, 4:4`
5，值 6	依次给位置 4、1 发下标 5（值 6）	`5:6`

所以输出的下标是 5 4 4 5 0。为什么发到的一定是“第一个”？因为从左往右走，在它出现之前，这个位置始终还在等；如果之前已经遇到更大的数，就早出栈了。

单调栈寻找右侧第一个更大元素

三、标准求解算法与模板代码

以下模板演示了如何利用单调栈高效寻找数组中每个元素右侧首个严格大于它的元素下标。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3000005;
int n,a[N],ans[N];

void solve(){
    stack<int> st;
    // 遍历每一个元素
    for(int i=1;i<=n;i++){
        // 维护单调递减栈，如果当前元素大于栈顶元素
        // 说明当前元素就是栈顶元素右侧第一个更大的数
        while(!st.empty()&&a[st.top()]<a[i]){
            ans[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }
    // 遍历结束后，还在栈里的元素说明右侧没有比它们更大的数
    // ans 数组默认初始化为 0，自然契合无解情况
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<(i==n?'\n':' ');
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    solve();
    return 0;
}

四、经典实战例题剖析与代码

针对高频衍生模型（区间最值贡献、视野遮挡、元素组合），以下通过几道进阶必刷题展现单调栈的实战威力。

1. 例题 1：P5788 【模板】单调栈

题意：给定一个长度为 $N$ 的数组，求每个元素右侧第一个大于它的元素下标。
考点：极简纯粹的单调栈基础应用。直接套用上述第三节的 solve() 函数模板即可，复杂度均摊 $O(N)$ 。

2. 例题 2：P2866 [USACO06NOV] Bad Hair Day S

题意： $N$ 头牛排成一列，每头牛都能看到右侧比自己矮的牛的头发，直到被一头大于等于自己身高的牛挡住视线。求所有牛能看到的头发数量总和。
分析：
1. 正向思考：求每头牛右侧能看到多少牛。
2. 逆向思考：求每头牛能被左侧多少头牛看到。
3. 维护一个单调递减栈。当处理到第 $i$ 头牛时，将其前面所有矮于或等于它的牛出栈（因为这些矮牛的视线被第 $i$ 头牛彻底阻挡，无法再看到后面的牛）。
4. 剔除无效数据后，此时栈中残留的元素，正是左侧所有比第 $i$ 头牛高、且视线未被遮挡的牛！因此，当前牛能被看到的次数就等于此时的栈内元素数量 st.size()。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=80005;
int n,a[N],ans;

void solve(){
    stack<int> st;
    for(int i=1;i<=n;i++){
        // 遇到大个子，将视线被挡住的矮个子弹出
        while(!st.empty()&&a[st.top()]<=a[i]) st.pop();
        // 栈中剩下的都是比当前牛高的，说明当前牛能被栈里的这些牛看到
        ans+=st.size();
        st.push(i);
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    solve();
    return 0;
}

3. 例题 3：P1901 发射站

题意： $N$ 个发射站排成一排，原题保证高度互不相同。每个发射站向左右两边发射能量 $V_i$ ，能量只能被两侧第一个比它高的发射站接收。求接收能量最多的发射站接收到了多少能量。
分析：
1. 问题本质是寻找每个元素左侧首个更高点和右侧首个更高点。
2. 依旧维护一个单调递减栈。考虑入栈和出栈时的两种相互作用：
  - 出栈时：当新站 $i$ 大于栈顶站 $top$ 时， $top$ 被弹出，说明 $i$ 就是 $top$ 右侧第一个比它高的站。所以 $i$ 会接收到 $top$ 的能量。
  - 入栈时：在把比 $i$ 矮的站都弹出后，如果栈非空，此时的新栈顶 $new\_top$ 必定是大于 $i$ 的，即 $new\_top$ 是 $i$ 左侧第一个比它高的站。所以 $new\_top$ 会接收到 $i$ 的能量。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000005;
int n,h[N],v[N],sum[N],ans;

void solve(){
    stack<int> st;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&h[st.top()]<h[i]){
            // 栈顶元素右侧第一个比它高的是 i
            sum[i]+=v[st.top()];
            st.pop();
        }
        if(!st.empty()){
            // 当前元素左侧第一个比它高的是此时的栈顶
            sum[st.top()]+=v[i];
        }
        st.push(i);
    }
    
    for(int i=1;i<=n;i++) ans=max(ans,sum[i]);
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i]>>v[i];
    solve();
    return 0;
}

4. 例题 4：P1823 [COI2007] Patrik 音乐会的等待

题意： $N$ 个人排队，只要中间没有比两人中较矮的那个人还高的人，他们就能互相看见。相等高度不挡视线。求能互相看见的对数。
分析：
1. 这是一道经典的视野与贡献模型，难点在于处理身高相等的情况。
2. 需要将 stack 中的元素聚合，存入结构体记录 <身高, 栈中相同身高的人数>。
3. 若当前人比栈顶高：这一组较矮的人都能看到当前人，答案加上这组人数；但再往右就被当前人挡住了，结算后出栈。
4. 若当前人和栈顶一样高：将栈顶的频次累加到答案中，并在此基础上继续往前看，检查是否有更高的那个人存在（有的话再加 1）。最终更新这一组相等身高的人数。

比如 [3,1,3]：后来的 3 先和中间的 1 配成一对，再和前面的 3 配成一对；这两个 3 随后合成一组。注意，这组人在原队伍里不一定挨着，是中间较矮的人弹出后凑到一起的。若所有人都一样高，每两个人都能互相看到，答案是 $n(n-1)/2$ ，所以用 long long。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
int n,a[N],ans;

struct Node{
    int h,cnt;
};

void solve(){
    stack<Node> st;
    for(int i=1;i<=n;i++){
        Node cur={a[i],1};
        // 遇到更高的，前面的矮子视线被阻断，结算答案并出栈
        while(!st.empty()&&st.top().h<cur.h){
            ans+=st.top().cnt;
            st.pop();
        }
        // 遇到一样高的，合并计数
        if(!st.empty()&&st.top().h==cur.h){
            ans+=st.top().cnt;
            cur.cnt+=st.top().cnt;
            st.pop();
        }
        // 还能看到左侧最近的那个更高的人，只再加一对
        if(!st.empty()){
            ans++;
        }
        st.push(cur);
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    solve();
    return 0;
}

五、进阶模型：边界扩张与区间贡献

前面几道题都是找单个“大哥”来结算。如果题目问的是一个区间属性，比如以某个数为最值的区间有多长、或者有多少个，单调栈同样能大显身手。它的工作变成了确定每个元素的“管辖边界”。

1. 柱状图中的最大矩形

💡 【实战例题】 给定 $n$ 个非负整数，用来表示各个柱子的高度，每个柱子宽度为 1。求在此柱状图中，能够勾勒出来的最大矩形面积。

核心推导： 如果我们要以第 $i$ 根柱子的高度 $h[i]$ 作为矩形的高度，这个矩形能向左右延伸多远？

往左，不能遇到比它矮的，所以左边界 $L[i]$ 是左侧第一个小于它的柱子位置。
往右，同理，右边界 $R[i]$ 是右侧第一个小于它的柱子位置。
矩形宽度为 $R[i] - L[i] - 1$ ，面积为 $h[i] \times (R[i] - L[i] - 1)$ 。

单调栈的魔法：一次遍历求出左右边界 我们维护一个单调不减栈，相等高度先留在栈里。当遇到一个新元素 $h[i]$ 小于栈顶元素 $h[top]$ 时，说明栈顶元素的“右侧首个更小值”找到了，就是 $i$ ！此时将 $top$ 弹出。弹出后，新的栈顶是谁？它是左侧留下来的、最近一个高度小于等于 $h[top]$ 的位置。没有等高柱子时，它就是“左侧首个更小值”；遇到等高柱子，先拿它作本次结算的左边界，更宽的范围留给后面弹出的同高度柱子。只需一次出栈操作，本次结算的左右边界就同时确定了。

哨兵技巧： 为了防止数组结束时栈里还有元素没结算，我们在数组首尾各加一个高度极小的“哨兵”。

首部加 -1：所有元素入栈前都有个垫底的，判断条件 h[top] > h[i] 绝不会把它弹出去，省去了判空的麻烦。
尾部加 -1：最后必然会把所有真正的非负高度柱子全部弹出结算，省去了循环后清理栈的代码。

（注：如果有连续相等高度，虽然先弹出的柱子算出的宽度偏小，但留在栈底的最后一个同高度柱子一定会算出跨越全局的最大宽度。因为是取最大值，所以不用担心重复覆盖问题。）

// 题目：柱状图中最大的矩形（经典模型）
// 输入范围：1 <= n <= 10^5, 0 <= h[i] <= 10^9
// 样例输入：
// 6
// 2 1 5 6 2 3
// 样例输出：
// 10
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100005;
int n, h[N], ans;

void solve(){
    h[0] = -1; // 首部哨兵，值设为极小值 (假设高度均为非负)
    h[n + 1] = -1; // 尾部哨兵，强制清算所有有效柱子
    stack<int> st;
    st.push(0); 
    
    // 连带尾部哨兵一起遍历
    for(int i = 1; i <= n + 1; i++) {
        // 维护单调递增栈
        while(h[st.top()] > h[i]) {
            int cur = st.top();
            st.pop();
            // 右边界是 i，左边界是弹出后的新栈顶
            int left = st.top();
            int right = i;
            int width = right - left - 1;
            ans = max(ans, h[cur] * width);
        }
        st.push(i);
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    solve();
    return 0;
}

2. 所有子数组最小值之和 (重复值归属问题)

💡 【实战例题】 给定一个非负整数数组 $A$ ，找到所有连续子数组的最小值，并返回这些最小值的总和，对 $10^9+7$ 取模。

核心推导： 如果强行枚举子数组是 $O(N^2)$ 的。转换视角：每个数字 $A[i]$ 作为最小值，能“统治”多少个子数组？假设 $A[i]$ 的左侧第一个比它小的位置是 $L$ ，右侧第一个比它小的位置是 $R$ 。在区间 $(L, R)$ 内，包含 $i$ 且最小值是 $A[i]$ 的子数组数量，刚好是： 左侧可选起点数 $\times$ 右侧可选终点数 $= (i - L) \times (R - i)$ 。 $A[i]$ 对总和的贡献就是 $A[i] \times (i - L) \times (R - i)$ 。

致命的重复值陷阱： 在上一题算最大面积时，区域重叠覆盖没关系，取 max 就能兜底。但这里是累加求和！看看这个数组：[2, 4, 2]。如果我们找的都是“严格小于”，第一个 2 找到的管辖区间是整个数组（管辖了 [2, 4, 2]），第二个 2 找到的管辖区间也是整个数组（也管辖了 [2, 4, 2]）。这样一来，子数组 [2, 4, 2] 的最小值 2 就被算了两次！

破局思路：一边严格，一边非严格 为了不重不漏，我们在代码里通过出栈条件的微调，隐式地规定：当遇到多个相等的最小值时，由最右边的那个元素来负责结算横跨它们的子数组。

右边界寻找：找小于或等于的元素（遇到等于我的，我就停下，把跨越我们的长区间让给右边的兄弟去管）。
左边界寻找：找严格小于的元素（遇到等于我的，我不停下，直接把它包进我的地盘）。

手推验证 [2, 4, 2]：

第一个 2（位置 1）：右边界找 <=，到了位置 3（第二个 2），停下！右边界是 3。左边界找 <，没找到，左边界是 0。包含它的子数组有：[2], [2, 4]。
第二个 2（位置 3）：右边界找 <=，一直到末尾，右边界是 4。左边界找 <，它往左看时，位置 1 的那个 2 刚才已经被它自己触发弹栈了！所以在栈里没人挡得住它，一路看到哨兵，左边界是 0。包含它的子数组有：[4, 2], [2], [2, 4, 2]。

完美！两者管辖的子数组没有交集，且刚好凑齐了所有包含 2 的组合。这正是单调栈令人着迷的数学对称美。代码中只要将出栈条件改为 a[st.top()] >= a[i] 即可。

// 题目：子数组的最小值之和 (如 LeetCode 907)
// 输入范围：1 <= n <= 10^5, 0 <= a[i] <= 10^9
// 样例输入：
// 4
// 3 1 2 4
// 样例输出：
// 17
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100005;
const int MOD = 1e9 + 7;
int n, a[N], ans;

void solve(){
    a[0] = -1; // 极小值保护栈底 (假设原数组均为非负数)
    a[n + 1] = -1; // 极小值触发全部弹栈
    stack<int> st;
    st.push(0);
    
    for(int i = 1; i <= n + 1; i++) {
        // 出栈条件改为 >=：
        // 右边界 right_bound 找到了 <= 它的位置
        // 弹出后的新栈顶 left_bound 肯定是 < 它的位置
        while(st.size() > 1 && a[st.top()] >= a[i]) {
            int cur = st.top();
            st.pop();
            
            int left = st.top();
            int right = i;
            
            // 先取模防止相乘时爆 long long
            int count = (cur - left) * (right - cur) % MOD;
            ans = (ans + a[cur] * count) % MOD;
        }
        st.push(i);
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    solve();
    return 0;
}

六、把几道题串起来

P5788：弹栈时，给旧位置记下“右侧第一个更大”的下标。
P2866：先弹掉不够高的牛，再数还有多少头牛看得到当前牛。挡住视线的那头牛不算被它看到的头发。
P1901：弹栈时结算右边的接收者，入栈前给左边的接收者送能量。
P1823：相等高度要合成一组，结算的是这一组的人数。

模板长得很像，关键却是：弹出时究竟在结算什么？相等的值该不该弹？ 每题先回答这两个问题，再写那个 while。

如果问题再加一句“只看最近 k 个位置”，最左边的旧候选还会过期。这就轮到下一讲的单调队列了。