给定一个数组，需要找到每个元素右边第一个比它大或者比它小的元素，暴力做法将会是平方的时间复杂度。如果利用单调栈，就能优化到线性的时间复杂度。本文将会对单调栈做具体的介绍，希望能让被单调栈困惑的读者豁然开朗。
本文封面由Power Point绘制，程序由gemini编写。
算法流程
单调栈能够高效地解决“寻找下一个/上一个更大/更小元素”这一类问题，具体可以归结为四种经典应用场景：寻找某个元素左侧第一个更大的元素、左侧第一个更小的元素、右侧第一个更大的元素，以及右侧第一个更小的元素。由于这四种场景在实现逻辑上具有高度的对称性，其核心思想完全一致，区别仅在于遍历方向与维持栈内单调性的不同。因此，为了让讲解更加聚焦和深入，本文将只剖析“寻找每个元素右边第一个更大的元素”这一种情况，当你完全掌握它之后，其余三种便能轻松地触类旁通。
算法的流程是，我们从左到右遍历数组，并借助一个栈来维护一个索引序列，该序列对应的元素值从栈顶到栈底呈单调递减。对于每一个新到来的元素 $nums[i]$，我们将其与栈顶索引所对应的元素进行比较：如果新元素更大，则说明我们找到了栈顶元素的“右边第一个更大元素”，此时我们将栈顶元素出栈，记录下它的答案，并用新元素继续与新的栈顶比较，如此循环；反之，如果新元素小于或等于栈顶元素，或者当上述循环结束后，我们就将当前元素的索引入栈，以维持栈的单调性，并让它也开始等待自己的“下一个更大元素”。整个数组遍历结束后，栈内剩余的索引所对应的元素，就是那些在右侧没有更大元素的数。算法流程图如下所示。
理论推导
算法正确性
我们可以通过反证法来证明该算法的正确性。设 $x$, $y$, $z$ 分别是位于索引 $i_x$, $i_y$, $i_z$ 的数组元素值。假设当位于 $i_y$ 的元素 $y$ 弹出位于 $i_x$ 的元素 $x$ 时，$y$ 并非 $x$ 右侧第一个更大的元素，那么在它们之间必然存在另一个元素 $z$ （位于索引 $i_z$ 满足 $i_x < i_z < i_y$），且其值 $z > x$。当算法从左到右遍历到 $z$ 时，由于 $x$ 此时仍在栈中，而栈内维护的单调递减性保证了当前栈顶元素的值必然小于或等于 $x$，因此根据 $z > x$ 的假设，可推断出 $z$ 一定大于栈顶元素。这必然会触发 while 循环，导致栈顶元素被弹出，此过程会持续进行直至 $x$ 本身也被 $z$ 弹出。这就产生了一个直接矛盾：我们的逻辑推论是 $x$ 必须在遇到 $z$ 时就被弹出，但这与我们最初的前提——$x$ 存活到了被更靠后的 $y$ 弹出——完全相悖。因此，最初的假设不成立，即 $x$ 和 $y$ 之间不可能存在比 $x$ 更大的元素，故 $y$ 一定是 $x$ 右侧遇到的第一个更大元素。
时间复杂度
简而言之：每个元素最多进栈一次、出栈一次。所有操作的总次数与元素数量 $n$ 成正比，因此总时间复杂度就是 $\mathcal{O}(n)$。
代码实现
#include <iostream>
#include <vector>
#include <stack>
/**
* @brief 使用单调栈解决“下一个更大元素”的问题
* @param n 数组的大小
* @param a 输入的数组 (1-based-indexed)
* @return 一个包含结果的数组，f[i] 是 a[i] 右侧第一个更大元素的下标
*/
std::vector<int> solve_monotonic_stack(int n, const std::vector<int>& a) {
// 1. 初始化结果数组，大小为 n+1 以便使用1-based索引。
// 题目要求若不存在则为0，因此默认值设为0。
std::vector<int> f(n + 1, 0);
// 2. 创建一个单调栈，用于存储元素的“索引”。
// 栈内索引对应的元素值，从栈顶到栈底保持单调递减。
std::stack<int> s;
// 3. 从左到右遍历数组
for (int i = 1; i <= n; ++i) {
// 4. 核心逻辑：当栈不为空，且当前元素 a[i] 大于栈顶索引对应的元素 a[s.top()]
while (!s.empty() && a[i] > a[s.top()]) {
// 找到了栈顶元素的答案，就是当前元素的索引 i
f[s.top()] = i;
// 栈顶元素已处理完毕，出栈
s.pop();
}
// 5. 当前元素的索引入栈，等待寻找它的下一个更大元素
s.push(i);
}
// 6. 循环结束后，栈内剩余的索引在数组右侧没有找到更大的元素。
// 由于结果数组 f 初始化时值就为 0，所以无需额外处理。
return f;
}
int main() {
// 针对大数据规模，开启快速 I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
// 使用 vector 存储输入，大小为 n+1，以适配题目的 1-based 索引
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}
// 调用单调栈函数解决问题
std::vector<int> result = solve_monotonic_stack(n, a);
// 按格式输出结果
for (int i = 1; i <= n; ++i) {
std::cout << result[i] << (i == n ? "" : " ");
}
std::cout << "\n";
return 0;
}