栈

栈是一种后进先出的线性数据结构
只有一端可以进出元素

模板

// tt表示栈顶，栈中第一个元素下标为1，便于处理边界情况
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt > 0)
{
}
// STL
stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

题目

括号的匹配

这题属于带优先级的括号匹配问题
做法是为每个括号增加一个数表示优先级，push的时候进行检查

#include <time.h>
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
char str[300];
int level(char op) {    // 优先级，数字越小优先级越高
    if (op == '{') {
        return 1;
    }
    else if (op == '[') {
        return 2;
    }
    else if (op == '(') {
        return 3;
    }
    else if (op == '<') {
        return 4;
    }
    else {
        return -1;
    }
}
int main() {
    #ifdef SUBMIT
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
    #endif
    int n;
    cin >> n;
    while (n--) {
        stack<pair<char, int>> s;
        scanf("%s", str);
        int len = strlen(str);
        for (int i = 0; i < len; i++) {
            int lv = level(str[i]);
            if (s.empty()) {
                s.push({str[i], lv});
            }
            else {
                auto op = s.top();
                if (    // 匹配上
                    (op.first == '{' && str[i] == '}')
                    or (op.first == '[' && str[i] == ']')
                    or (op.first == '(' && str[i] == ')')
                    or (op.first == '<' && str[i] == '>')
                ) {
                    s.pop();
                }
                else {    // 满足优先级限制
                    if (lv >= op.second) {
                        s.push({str[i], lv});
                    }
                    else {
                        break;
                    }
                }
            }
        }
        if (s.empty()) {    // 仍有括号没有匹配上
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
    #ifdef SUBMIT
    long _end_time = clock();
    printf("\n\ntime = %ld ms", _end_time - _begin_time);
    #endif
    return 0;
}

包含min函数的栈

这题在栈的基础上需要支持O(1)时间内查询最小值
小根堆只能做到O(logn)
如果只用一个变量记录最小值，出账时刚好弹出该最小值，那么需要重新遍历获得最小值
因此可以增加一个栈，用于保存原栈中从栈底到每个位置的最小值

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> st, st_min;
    MinStack() {
    }
    void push(int x) {
        st.push(x);
        if (st_min.size()) x = min(x, st_min.top());
        st_min.push(x);
    }
    void pop() {
        st.pop();
        st_min.pop();
    }
    int top() {
        return st.top();
    }
    int getMin() {
        return st_min.top();
    }
};

编辑器

四种操作都在光标处发生，并且操作完成光标至多移动一个位置
这题与动态中位数的思想类似，用到了对顶栈
栈A存储从序列开头到光标，B存储从序列结尾到光标
查询最大前缀和仿照上一题，增加一个栈维护

#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;
const int N = 1e6 + 10;
int stl[N], str[N], tl, tr;
int s[N], s_max[N];
int q;
void push_left(int x) {
    stl[++tl] = x;
    s[tl] = s[tl - 1] + x;
    s_max[tl] = max(s_max[tl - 1], s[tl]);
}
int main() {
    s_max[0] = INT_MIN;
    cin >> q;
    while (q--) {
        char op[2];
        scanf("%s", op);
        if (op[0] == 'I') {
            int x;
            scanf("%d", &x);
            push_left(x);
        }
        else if (op[0] == 'D') {
            if (tl > 0) tl--; 
        }
        else if ('L' == op[0]) {
            if (tl > 0) str[++tr] = stl[tl--];
        }
        else if ('R' == op[0]) {
            if (tr > 0) push_left(str[tr--]);
        }
        else {
            int k;
            scanf("%d", &k);
            printf("%d\n", s_max[k]);
        }
    }
    return 0;
}

进出栈序列问题

法一
- 搜索：对于任何一个状态，两种选择：
  - 下一个数进栈
  - 栈顶数出栈
- 用递归进行枚举，复杂度O(2^N)
法二
- 动态规划：每个时刻我们只关心当前有多少个数未进栈，多少个数未出栈，与这些数具体是什么无关
- 用F[i, j]表示i个数尚未进栈，j个数尚未出栈
- 目标：F[N, 0]
- 边界：F[0, 0] = 1
- 转移方程：F[i, j] = F[i - 1, j + 1] + F[i, j - 1]
法三
- 递推：考虑“1”这个数在出栈序列中的位置为k
- 序列的进出栈过程为：
  - 1入栈
  - 2~k进出栈
  - 1出栈
  - k + 1~N进出栈
- 原问题就变成了k-1个数和N-k个数进出栈这两个子问题
法四
- 该问题等价于求第N项卡特兰数，即
- 由于本题数据量较大，需要用质因数分解，将除法改成乘法，并且利用压位 ```cpp
  include
  include

using namespace std;

typedef long long LL;

const int N = 60000 * 2 + 10, M = 1e9; // 压位

int primes[N], cnt; bool st[N]; int powers[N];

void get_primes(int n) { // 线性筛法求质数 for (int i = 2; i <= n; i++) { if (!st[i]) primes[cnt++] = i; for (int j = 0; primes[j] <= n / i; j++) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } }

int get(int n, int p) { // 求n!中的质数p的出现次数 int res = 0; while (n) { res += n / p; n /= p; } return res; }

void mul(vector &a, int b) { // 高精度乘法 + 压位 LL t = 0;

for (int i = 0; i < a.size(); i++) {
    a[i] = a[i] * b + t;
    t = a[i] / M;
    a[i] %= M;
}
while (t) {
    a.push_back(t % M);
    t /= M;
}

}

void out(vector &a) { // 输出，注意压位第一个单独输出，不要前导0 printf(“%lld”, a.back()); for (int i = a.size() - 2; i >= 0; i—) printf(“%09d”, a[i]); }

int main() { int n; cin >> n;

get_primes(2*n);
for (int i = 0; i < cnt; i++) {    // 分子质数p数目-分母
    int p = primes[i];
    powers[p] = get(2 * n, p) - get(n, p) * 2;
}
int tmp = n + 1;
for (int i = 0; i < cnt && primes[i] <= tmp; i++) {    // 去掉n+1中质数数目
    int p = primes[i];
    while (tmp % p == 0) {
        tmp /= p;
        powers[p]--;
    }
}
vector<LL> res;
res.push_back(1);
for (int i = 0; i < cnt; i++) {    // 质数幂次相乘
    int p = primes[i];
    for (int j = 0; j < powers[p]; j++) {
        mul(res, p);
        // out(res);
        // cout << endl;
    }
}
out(res);
return 0;

}

<a name="9BdpO"></a>
# 单调栈
在栈的基础上维护这样一个性质：栈中数具备单调性<br />常见题型：找出每个数左边/右边离它最近的比它大/小的数
<a name="IGlhy"></a>
## 模板
```cpp
int tt = 0;
for (int i = 1; i <= n; i ++ )
{    // 可以考虑预先向栈中Push一个最小/最大的数，作哨兵
    while (tt && check(stk[tt], i)) tt -- ;    // 不满足单调性质就出栈
    stk[ ++ tt] = i;
}

题目

直方图中最大的矩形

这题就是要找出当前矩阵左边/右边离它最近的高度比它底的矩阵
可以用两个单调栈分别维护左边和右边

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int n;
int h[N], l[N], r[N];
void get(int *rec) {
    stack<int> st;
    h[0] = -1;    // 哨兵！
    st.push(0);
    for (int i = 1; i <= n; i++) {
        while (h[st.top()] >= h[i]) st.pop();
        rec[i] = st.top() + 1;
        st.push(i);
    }
}
int main() {
    while (cin >> n, n) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &h[i]);
        }
        get(l);
        reverse(h + 1, h + n + 1);    // 逆序，求右边的转化成求左边的
        get(r);
        LL ans = 0;
        for (int i = 1, j = n; i <= n; i++, j--) {
            ans = max(ans, (LL)h[i] * (n - l[j] + 1 - r[i] + 1));    // 注意坐标转换，建议纸上演算！
        }
        printf("%lld\n", ans);
    }        
    return 0;
}