数组模拟栈+最小值栈

#include <iostream>

using namespace std;
const int N = 1000010;

int n, tt, stk[N], tt2, m[N];                                   // 1

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (; n --;) {
        string s;
        cin >> s;
        int x;
        if (s == "push") {
            cin >> x;
            stk[++ tt] = x;                                     // 2
            if (!tt2 || x <= m[tt2]) m[++ tt2] = x;             // 3
        } else if (s == "pop") {
            if (stk[tt] == m[tt2]) tt2 --;                      // 4
            tt --;                                              // 5
        } else if (s == "getMin") {
            cout << m[tt2] << endl;                             // 6
        }
    }
    return 0;
}

1. 维护两个栈 stk 和 m ,分别存放 push 的数字，和 push 之后所有数的最小值。
2. 栈顶右移并把 x 入栈
3. 当最小值栈 m 为空或者当 x 小于最小值栈的栈顶时，说明此时出现了新的最小值，将其入栈。
4. 如果待 pop 的数是最小值，那么我们连同最小值栈一起弹出栈顶；否则当前状态的最小值没有在最小值栈中，只需将 stk 栈顶弹出。
5. stk 栈顶弹出。
6. 输出栈顶。