栈

模拟栈

可以用一个定长数组+一个栈顶指针来模拟栈：

const int N = 1e5 + 7;

int stk[N], tt = -1; // tt => top指针，指向栈顶

stk[++ tt] = x;      // push

tt --;               // pop

stk[tt];             // top

if(tt >= 0)          // not empty
else                 // empty

385. 迷你语法分析器

单调栈

单调栈即满足单调性的栈结构，单调栈主要用于在$O(n)$内解决NGE问题（Next Greater Element）。

NGE问题：对于序列中的每个元素，找到下一个(或上一个)比当前元素大(或小)的元素。

逆向遍历时，单调栈中存的是有可能成为前一个元素右边界的元素

#include <vector>
#include <stack>
#include <iostream>

using namespace std;

vector<int> arr;
int n;

int main() {
    cin >> n;
    arr.resize(n + 1);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    
    vector<int> f(n + 1);
    stack<int> S;
    for (int i = n; i >= 1; i --) {
        while (!S.empty() && arr[S.top()] <= arr[i]) {
            S.pop(); // 弹出栈顶比当前数小的
        }
        // 说明当前arr[S.top()] > arr[i]
        f[i] = S.empty() ? 0 : S.top();
        S.push(i);
    }
    
    for (int i = 1; i <= n; i ++) {
        printf("%d ", f[i]);
    }
    
    return 0;
}

正向遍历时，栈中存的是还未找到右边界的元素

解决的暴力问题

变种？

有关单调栈的题目很灵活：单调栈的构造是固定模板，但实际问题的处理逻辑确是千变万化的，需要清晰的思维。

你要想清楚以下三个问题，才能掌握好单调栈：

• 为什么能用单调栈？(是否需要构造单峰/\ $or$ 单谷\/)
• 单调性是否需要严格？
• 实际问题的逻辑该怎么处理？

接雨水

Acwing-1574.接雨水

根据题意可知，需要构造一个单谷\/（中间低两边高)才能接到雨水，因此可以构造一个严格单调递减的单调栈来完成这个操作，并且对于当前的每个谷底$cur$，其能接到的雨水面积$S_{area}$为：

$S_{area} = w * h = (r - l - 1) * (min(height[l], height[r]) - height[cur])$

如果没有形成单谷\/，无法接到雨水，那么遍历完后留在单调栈中的数不弹出来也行，对计算结果无影响。

#include <stack>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int n;
vector<int> height;
stack<int> S;

int main() {
    cin >> n;
    height.resize(n);
    for (int i = 0; i < n; i ++) {
        scanf("%d", &height[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i ++) {
        while (!S.empty() && height[S.top()] <= height[i]) {
            int cur = S.top();
            S.pop();
            if (S.empty()) break;   // 左侧不存在，无法构成单谷
            int r = i;
            int l = S.top(); 
            res += (r - l - 1) * (min(height[r], height[l]) - height[cur]);
        }
        S.push(i);
    }

    cout << res << endl;
    return 0;
}

直方图中的最大矩形

Acwing-131.直方图中的最大矩形

根据题意，需要构造一个单峰/\（中间高两边低）才能计算出$cur$矩形的最大面积，因此可以构造一个严格单调递增的单调栈来完成这个操作，并且对于当前的每个谷峰$cur$，其能形成的最大矩形面积$S_{area}$为：

$S_{area} = w * h = (r - l - 1) * height[cur]$

如果没有形成单峰"/\，其实当前单个上升区间/也能计算矩形面积，那么就有必要把遍历完后留在单调栈中的数全部弹出来算一次，但这样会导致代码冗余（逻辑重复），因此可以添加一个尾部哨兵来统一操作。

#include <stack>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

vector<int> height;
stack<int> S;

int main() {
    int n;
    while (scanf("%d", &n), n) {
        height.resize(n);
        
        for (int i = 0; i < n; i ++) {
            scanf("%d", &height[i]);
        }
        
        height.push_back(0);       // 尾部哨兵
        n = height.size();

        LL res = 0;
        S = stack<int>();
        for (int i = 0; i < n; i ++) {
            while (!S.empty() && height[S.top()] >= height[i]) {
                int cur = S.top();
                S.pop();
                int r = i;  
                int l = S.empty() ? -1 : S.top();
                res = max(res, (r - l - 1) * (LL)height[cur]);
            }
            S.push(i);
        }       

        // 如果没有尾部哨兵，需要添加以下代码，计算留在单调栈中的上升区间
        // while (!S.empty()) {
        //     int cur = S.top();
        //     S.pop();
        //     int r = n;  
        //     int l = S.empty() ? -1 : S.top();           
        //     res = max(res, (r - l - 1) * (LL)height[cur]);
        // }
        
        cout << res << endl;
    }
    
    return 0;
}

$\left \lceil 接雨水 \right \rfloor$和$\left \lceil直方图中的最大矩形\right \rfloor$这两道题很相似，宽度都是用$r - l - 1$来求。