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

问题分析

本题要求对数组中的每个元素，找到其右侧第一个大于它的元素的下标。这是一个经典的"下一个更大元素"问题，单调栈是解决此类问题的最优数据结构。

单调栈核心概念

单调栈是一种特殊的栈，其中元素保持单调性（单调递增或单调递减）。在本题中，我们需要维护一个单调递减栈（从栈底到栈顶，元素值严格递减）。

单调栈的工作原理

入栈规则：
- 新元素入栈前，弹出所有破坏单调性的栈顶元素
- 保持栈中元素值严格单调递减
关键性质：
- 栈中元素对应的值：a[st[0]] > a[st[1]] > ... > a[st[top]]
- 栈中元素的下标：st[0] < st[1] < ... < st[top]（因为从右向左遍历）

算法步骤详解

1. 从右向左遍历

为什么从右向左？因为我们关心的是右侧元素
当处理位置i时，栈中已包含i+1到n的"有效候选"

2. 维护单调递减栈

弹出阶段：弹出所有小于等于a[i]的元素
```
while (!st.empty() && a[st.top()] <= a[i]) {
    st.pop();
}
```
- 为什么弹出？ 这些元素不可能成为左侧元素的答案：
  - 它们比a[i]小（或相等）
  - 且位置在i右侧（比i更远）
  - a[i]比它们更近且更大，完全"遮挡"了它们

确定答案：

if (!st.empty()) f[i] = st.top(); // 栈顶即为答案
else f[i] = 0; // 无更大元素

入栈阶段：

st.push(i); // 当前元素成为新的候选

代码实现

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    // 输入输出优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n + 1);  // 1-indexed数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> f(n + 1, 0);  // 存储结果
    stack<int> st;            // 单调栈，存储下标
    
    // 从右向左遍历
    for (int i = n; i >= 1; i--) {
        // 弹出所有不大于当前元素的栈顶元素（破坏单调性的元素）
        while (!st.empty() && a[st.top()] <= a[i]) {
            st.pop();
        }
        
        // 确定f(i)的值
        if (!st.empty()) {
            f[i] = st.top();  // 栈顶即为右侧第一个更大元素
        } else {
            f[i] = 0;         // 不存在更大元素
        }
        
        // 当前下标入栈，保持单调递减性
        st.push(i);
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << f[i];
        if (i < n) cout << ' ';
        else cout << '\n';
    }
    
    return 0;
}

代码详解

1. 单调栈维护

while (!st.empty() && a[st.top()] <= a[i]) {
    st.pop();
}

关键点：使用<=而非<
- 当遇到相等元素时，右侧的相等元素不可能成为左侧元素的答案
- 例如：[3, 3, 4]中，第一个3的右侧第一个更大元素是4，而非第二个3

2. 边界处理

栈为空时，f[i] = 0（根据题目来，也可以-1表示没有进行标记）
使用1-indexed数组，与题目描述一致

扩展思考

1. 变种问题

左侧第一个更大元素：改为从左向右遍历
下一个更小元素：改为维护单调递增栈
循环数组：将数组复制一份接在后面

2. 单调栈的通用模板

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);  // 默认值-1，根据题目调整
    stack<int> st;
    
    for (int i = n-1; i >= 0; i--) {
        while (!st.empty() && nums[st.top()] <= nums[i]) {
            st.pop();
        }
        if (!st.empty()) res[i] = st.top();
        st.push(i);
    }
    return res;
}

哨兵优化

优化思想：在数组末尾添加一个极大值作为哨兵，消除边界条件检查，使代码更简洁高效。

哨兵下标设为 $0$ （对应题目中 $f(i)=0$ 的含义）
当答案为哨兵位置时，将其转换为 $0$

算法步骤：

在数组末尾添加极大值哨兵 $a_{n+1} = +\infty$
将哨兵下标 $n+1$ 压入栈
从 $n$ 到 $1$ 遍历：
- 弹出所有值 $\leq a_i$ 的元素（哨兵保证栈永不为空）
- $f(i) = \begin{cases} 0 & \text{if 栈顶是哨兵} \\ \text{栈顶} & \text{otherwise} \end{cases}$
- 将 $i$ 压入栈
输出 $f(1)$ 到 $f(n)$

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n + 2); // 额外空间用于哨兵
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 设置右侧哨兵：极大值
    a[n + 1] = 2e9; // 大于题目中任何可能的值
    
    vector<int> f(n + 1, 0);
    stack<int> st;
    st.push(n + 1); // 先将哨兵入栈，确保栈非空
    
    // 从右向左遍历
    for (int i = n; i >= 1; i--) {
        // 弹出所有不大于当前元素的元素（哨兵保证栈不为空）
        while (a[i] >= a[st.top()]) {
            st.pop();
        }
        // 确定f(i)：如果栈顶是哨兵，则答案为0
        f[i] = (st.top() == n + 1) ? 0 : st.top();
        st.push(i);
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << f[i] << (i < n ? ' ' : '\n');
    }
    
    return 0;
}

从左向右遍历

核心思想：从左向右遍历时，栈中存储的是尚未找到答案的元素下标。当遇到大于栈顶元素的值时，确定栈顶元素的答案。

本质是"延迟确定答案"：当前元素是前面某些元素的答案
栈中元素对应的值严格单调递减

算法步骤：

初始化空栈和结果数组 $f$ （默认值为 $0$ ）
从 $1$ 到 $n$ 遍历：
- 当栈非空且 $a_i > a_{\text{栈顶}}$ ：
  - $f(\text{栈顶}) = i$
  - 弹出栈顶
- 将 $i$ 压入栈（等待后续更大元素）
栈中剩余元素的 $f$ 值保持为 $0$
输出 $f(1)$ 到 $f(n)$

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> f(n + 1, 0); // 默认值为0
    stack<int> st;           // 存储待确定答案的下标
    
    // 从左向右遍历
    for (int i = 1; i <= n; i++) {
        // 当前元素是栈中某些元素的答案
        while (!st.empty() && a[i] > a[st.top()]) {
            f[st.top()] = i; // 确定栈顶元素的答案
            st.pop();        // 已确定答案，弹出
        }
        st.push(i); // 当前元素等待后续更大元素
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << f[i] << (i < n ? ' ' : '\n');
    }
    
    return 0;
}

复杂度分析

时间复杂度： $O(n)$
- 每种方法中，每个元素最多入栈和出栈一次
- 总操作次数不超过 $2n$
空间复杂度： $O(n)$
- 结果数组 $f$ ： $O(n)$
- 单调栈：最坏情况 $O(n)$ （整个数组单调递减）

推荐选择：

作为通用解法，从右向左遍历最为直观
对性能要求极高时，哨兵优化可消除分支预测
在需要与其它算法（如滑动窗口）结合时，从左向右遍历可能更自然