单调栈

🌲 引入¶

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

为了描述方便，以下举例及伪代码以维护一个整数的单调递增栈为例。

⚙️ 单调栈操作过程¶

🔼 插入元素¶

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

例如，栈中自顶向下的元素为 ${0,11,45,81}$。

插入元素 $14$ 时为了保证单调性需要依次弹出元素 $0,11$，操作后栈变为 ${14,45,81}$。

伪代码如下：

insert x
while !stk.empty() && stk.top() < x // 先将小于 x 的全部出栈
    stk.pop()
sta.push(x)

🧩 单调栈应用¶

📘 下一个更大元素（Next Greater Element）

对每个位置 $i$，求其右侧第一个大于或等于 $a_i$ 的下标 $r_i$，若不存在则 $r_i=n+1$。

📙 下一个更小元素（Next Smaller Element）

对每个位置 $i$，求其右侧第一个小于或等于 $a_i$ 的下标 $r_i$，若不存在则 $r_i=n+1$。

📗 前一个更大元素（Previous Greater Element）

对每个位置 $i$，求其左侧第一个大于或等于 $a_i$ 的下标 $l_i$，若不存在则 $l_i=0$。

📕 前一个更小元素（Previous Smaller Element）

对每个位置 $i$，求其左侧第一个小于或等于 $a_i$ 的下标 $l_i$，若不存在则 $l_i=0$。

🎯 常见例题¶

📍 1. 下一个更大元素（Next Greater Element）¶

题目： 对长度为 $n$ 的数组 $a[1\ldots n]$，求每个位置 $i$ 右侧第一个比它大的元素下标 $r_i$，若不存在则 $r_i=n+1$。

❌ 暴力做法：

for (int i = 1; i <= n; i++) r[i] = n + 1;
for (int i = 1; i <= n; i++)
{
    for (int j = i+1; j <= n; j++)
    {
        if (a[j] > a[i])
        {
            r[i] = j;
            break;
        }
    }
}

时间复杂度 $O(n^2)$，最坏情况下会有 $\Theta(n^2)$ 次比较。

✅ 单调栈优化：

注意到：当我们扫描到某个大元素 $a[k]$ 时，位于它之前且比它小的一段下标序列 $i_1<i_2<\cdots<i_m<k$ 满足：

\[ a[i_1]>a[i_2]>\cdots>a[i_m]<a[k]. \]

那么 $a[k]$ 就是它们所有人的 下一个更大元素，可一次性赋值 $r_{i_1}=r_{i_2}=\cdots=r_{i_m}=k$。

这启发我们用 单调栈 来批量解决这些查询。

维护策略：

维护一个 存下标 的栈 $\text{stk}$，保证从栈顶到栈底对应值 $\uparrow$（单调递增）
扫描 $i=1$ 到 $n$：
- 当栈非空且 $a[\text{stk.top()}] < a[i]$ 时：
  - 弹出栈顶下标 $j=\text{stk.top()}$，设 $r_j=i$
- 重复上述弹出，直至栈空或顶部值 $\ge a[i]$
- 最后将 $i$ 入栈，等待它的 下一个更大元素

算法流程：

stack 实现

for (int i = 1; i <= n; i++) r[i] = n + 1;
stack<int> stk;
for (int i = 1; i <= n; i++)
{
    while (!stk.empty() && a[stk.top()] < a[i])
    {
        r[stk.top()] = i;
        stk.pop();
    }
    stk.push(i);
}

数组模拟栈 实现

for (int i = 1; i <= n; i++) r[i] = n + 1;
int top = 0; // 维护栈顶
for (int i = 1; i <= n; i++)
{
    while (top && a[stk[top]] < a[i])
    {
        r[stk[top]] = i;
        top--;
    }
    stk[++top] = i;
}

vector 充当栈

for (int i = 1; i <= n; i++) r[i] = n + 1;
vector<int> stk;
for (int i = 1; i <= n; i++)
{
    while (!stk.empty() && a[stk.top()] < a[i])
    {
        r[stk.top()] = i;
        stk.pop_top();
    }
    stk.push_back(i);
}

每个下标最多进出栈一次，时间复杂度为 $O(n)$。

同理可得上一个更大的求法

for (int i = 1; i <= n; i++) l[i] = 0;
int top = 0;
for (int i = n; i >= 1; i--)
{
    while (top && a[i] > a[stk[top]])
    {
        l[stk[top]] = i;
        top--;
    }
    stk[++top] = i;
}

📍 2. 下一个更小元素与上一个更小元素¶

题目： 给定数组 $a[1\ldots n]$，对每个位置 $i$ 求：

\[\begin{aligned} &L_i = \max\{j<i \mid a[j]<a[i]\}\\ &R_i = \min\{j>i \mid a[j]<a[i]\} \end{aligned}\]

若不存在则分别令 $L_i=0,\,R_i=n+1$。

➤ 求右侧第一个更小

从左向右一次扫描，维护 单调递减 的下标栈（栈顶 $\to $ 栈底对应值递减）

遍历 $i=1\ldots n$，令初始 $R_i=n+1$
当栈非空且 $a[\text{stk.top()}] > a[i]$ 时:
- 弹出 $j=\text{stk.top()}$，设 $R_j = i$
将 $i$ 入栈，继续扫描。

每个下标最多入/出栈一次，总体 $O(n)$。

for (int i = 1; i <= n; i++) 
    l[i] = 0, r[i] = n + 1;
top = 0;
for (int i = 1; i <= n; i++)
{
    while (top && a[stk[top]] > a[i])
    {
        r[stk[top]] = i;
        top--;
    }
    stk[++top] = i;
}

➤ 求左侧第一个更小

从右向左一次扫描，维护 单调递减 的下标栈（栈顶 $\to $ 栈底对应值递减）

遍历 $i=n\ldots 1$，令初始 $l_i=0$
当栈非空且 $a[\text{stk.top()}] > a[i]$ 时:
- 弹出 $j=\text{stk.top()}$，设 $l_j = i$
将 $i$ 入栈，继续扫描。

每个下标最多入/出栈一次，总体 $O(n)$。

top = 0; // 清空栈
for (int i = n; i >= 1; i--)
{
    while (top && a[stk[top]] > a[i])
    {
        l[stk[top]] = i;
        top--;
    }
    stk[++top] = i;
}

📐 3. 直方图中最大矩形面积¶

题目： 给定高度数组 $h[1\ldots n]$，求最大矩形面积。

✅ 思路：

对每个柱子 $i$ 作为 最低高度 枚举
找到左右两边第一个高度 $< h_i$ 的位置 $L_i, R_i$
计算面积 $= h_i \times (R_i - L_i - 1)$

最终答案为所有柱子的最大面积：

\[ \text{Area}_i = \max(h_i \times (R_i - L_i - 1)) \]

🧮 4. [COCI 2010/2011 #3] DIFERENCIJA¶

给定数组 $a[1\ldots n]$，计算

计算：

\[ \sum_{1\le i\le j\le n} \bigl(\max_{i\le k\le j}a_k \,-\, \min_{i\le k\le j}a_k\bigr). \]

🧠 等价于：

\[ S_{\max} \;-\; S_{\min}, \quad S_{\max}=\sum_{i=1}^n\sum_{j=i}^n\max_{i\le k\le j}a_k. \]

我们只讨论 $S_{\max}$ 的计算。

❌ 暴力思路：

枚举区间：$O(n^2)$ 无法承受。
- 枚举区间的同时还需要求区间的 $\max$。
复杂度：$O(n^3)$

✅ 贡献法：枚举最大值

对于每个位置 $i$，统计有多少子区间以 $a_i$ 为最大值，记作 $\mathit{cnt}_i$。这就是贡献法的体现，计算每个数值对答案的贡献。

\[ S_{\max} = \sum_{i=1}^n \bigl(\mathit{cnt}_i \times a_i\bigr). \]

关键：高效求出 $\mathit{cnt}_i$。

若以 $a_i$ 为 严格最大值，则子区间左右边界 $x\le i\le y$ 必须满足：

\[ \max_{x\le k<i} a_k < a_i, \quad \max_{i<k\le y} a_k \le a_i. \]

设

\[ L_i = \max\{\,j<i \mid a_j>a_i\},\quad R_i = \min\{\,j>i \mid a_j\ge a_i\} \]

可选左端点数为 $(i - L_i)$，右端点数为 $(R_i - i)$：

\[ \mathit{cnt}_i = (i - L_i)\times (R_i - i) \]

🧩 为何左侧是 $a_j>a_i$，右侧是 $a_j\geq a_i$? 为避免重复计算，例如 [7, 5, 7, 5]，可以自行体会。

📌 代码实现：

for (int i = 1; i <= n; i++) 
{
    cin >> a[i];
    l[i] = 0, r[i] = n + 1;
}
for (int i = 1; i <= n; i++) 
{
    while (top && a[i] >= a[stk[top]]) 
    {
        r[stk[top]] = i; // 对于栈顶来说，右侧第一个大于或等于自己的就是 a[i]
        top--;
    }
    l[i] = stk[top]; // 小于或等于 a[i] 的都出栈了，因此栈顶就是位置 i 左侧第一个大于 a[i] 的位置
    stk[++top] = i;
}
long long mx = 0;
for (int i = 1; i <= n; i++)
{
    mx += 1ll * a[i] * (i - l[i]) * (r[i] - i); // 计算每个 a[i] 对答案的贡献
}

5. 求数列的所有后缀最大值的位置¶

下标 $i$ 不是后缀最大值，当且仅当 $a_i$ 后面有不小于它的数 $a_j$。那么此时后面不管输入多少个数字，都有 $a_i\leq a_j$，那么 $i$ 就不可能是后缀最大值了。

如上图，我们把数列中每个数都看作一个人，所有人都向后看，如果看到队尾，就说明这个人的下标是后缀最大值。如果一个人看不到队尾，说明有人把他挡住了，那么他就不可能再看到队尾了，此时我们可以把他移出数列。

每个人进入数列时都会挡住所有比他矮的人，此时，移出所有比他矮的人。那么易知数列总是单调递减的。所以当我们需要移出人的时候，只需要从队尾移出，直到队尾的人比要进来的人高。

这不就是单调栈吗？（从栈顶到栈底单调递增）

栈顶是位置靠后的元素，栈底是位置靠前的元素。
因此从顶到底单调递增，说明栈底靠前的位置没有被挡住。

异或运算最重要的性质就是自反性。

也就是 $a\oplus b\oplus b=a$

我们维护的单调栈中都是当前的后缀最大值，所以当有人被移出或进入时，将答案与他的下标做异或运算即可。

for (int i = 1; i <= n; i++)
{
    cin >> a[i];
    // 栈顶会被 a[i] 挡住，因此移除
    while (top && a[i] >= a[stk[top]])
    {
        ans ^= stk[top];
        top--;
    }
    ans ^= i;
    stk[++top] = i;
    cout << ans << "\n";
}

总结本质上单调栈维护的是数列所有前缀的后缀最值。你可以通过调整比较条件里的大于号、小于号、大于等于号、小于等于号来用这一数据结构维护所有前缀的后缀最大、最小、非严格最大、非严格最小值。

6. [ABC372D] Buildings¶

题意： 给定 $n$ 个数字 $a_1,a_2,\ldots,a_n$。

对于每一个 $i$，求有多少个 $j$ 满足：

$i<j\leq n$
$[i,j-1]$ 之间的所有数字都小于 $a_j$。

思路：

记 $l_i$ 为 $i$ 左侧第一个 严格大于 自己的位置。

考虑枚举 $j$，那么根据 $l_j$ 的定义，当 $i\in [l_j+1,j-1]$ 时，这些 $i$ 都是满足条件的。

使用 $ans[i]$ 维护最终的答案，则 $ans[l_j+1],\ldots,ans[j-1]$ 都会增加 $1$。

使用差分 $O(1)$ 更新即可。

整体时间复杂度：$O(n)$。

单调栈