[

    ](https://www.luogu.com.cn/problem/P4147)
    eg：对序列中的第 i 个元素求出该元素后面第一个大于 a[i] 的元素下标

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. using namespace std;
    4. const int N = 3e6+5;
    5. int n;
    6. int a[N], f[N];
    7. stack<int> stk; 
    8. signed main() {
    9.     cin >> n;
    10.     for (int i = 1; i <= n; i++)
    11.         scanf("%lld", &a[i]);
    12.     for (int i = n; i >= 1; i--) {
    13.         while (stk.size() && a[i]>=a[stk.top()]) 
    14.             stk.pop();
    15.         f[i] = stk.size()?stk.top():0;
    16.         stk.push(i);
    17.     }
    18.     for (int i = 1; i <= n; i++) 
    19.         cout << f[i] << " \n"[i==n];
    20.     return 0;
    21. }

    eg：直方图最大矩阵

    https://www.acwing.com/problem/content/description/133/

    维护一个升序的单调栈，从前往后遍历，当遇到当前方块高度小于上一个方块高度时，找到前面第一个高度小于当前方块的方块，因为中间的方块一定是单调上升的形式，所以可以将中间的连续方块按如下处理（从后往前每次计算出当前高度乘上比他高的方块的宽度累加，不断更新最大值即可），然后让当前方块的宽加上被弹出栈的方块宽度之和
    image.png
    对于最后剩下的单调部分，像前面一样处理即可
    image.png

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. using namespace std;
    4. const int N = 1e5+5;
    5. int a[N]; 
    6. struct node {
    7.     int h, w;
    8. };
    9. signed main() {
    10.     int n;
    11.     while (cin >> n, n) {
    12.         int ans = 0;
    13.         for (int i = 1; i <= n; i++)
    14.         scanf("%lld", &a[i]);
    15.         stack<node> stk;
    16.         stk.push({a[1], 1});
    17.         int tmp = 0, mx = 0;
    18.         for (int i = 2; i <= n; i++) {
    19.             tmp = 0;
    20.             while (stk.size() && stk.top().h>=a[i]) {
    21.                 tmp += stk.top().w;
    22.                 mx = max(mx, stk.top().h*tmp);
    23.                 stk.pop();    
    24.             }
    25.             stk.push({a[i], tmp+1});
    26.         }
    27.         tmp = 0;
    28.         while (stk.size()) {
    29.             tmp += stk.top().w;
    30.             mx = max(mx, stk.top().h*tmp);
    31.             stk.pop();
    32.         }
    33.         ans = max(ans, mx);
    34.         cout << ans << '\n';
    35.     }
    36.     return 0;
    37. }

    eg：接雨水

    https://www.acwing.com/problem/content/description/1576/
    维护一个降序的单调栈，弹出所有比当前方块高度低的方块，若弹出方块候前面还有方块则累加雨水量
    image.png

    #include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

int a[N];

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int ans = 0; 
    stack<int> stk;
    for (int i = 1; i <= n; i++) {
        while (stk.size() && a[i]>a[stk.top()]) {
            int tmp = stk.top();
            stk.pop();
            if (stk.size()) {
                int len = i-stk.top()-1;
                int h = min(a[i], a[stk.top()])-a[tmp];
                ans += len*h;
            }
        }
        stk.push(i);
    }
    cout << ans << '\n';
    return 0;
}