题解 | #最小栈#

可以不使用线性的额外空间，只需要O(1)的额外空间复杂度：
· 记录minx，表示当前最小值。push(x)时，判断x是否大于minx。
· 使用栈s，push的不是原始插入值，而是差值：x-minx。
若x>=minx，则皆大欢喜，直接push(x-minx)，不需要修改minx。对应的pop也一样，直接加回去即可。
若x<minx，则x-minx < 0，在push(x-minx)后顺便更新minx。对应的pop也是逆运算。

#include <stdio.h>
#include <stack>
#include <algorithm>

struct MinStack {
    std::stack<int> s;
    int minx = 0;

    MinStack() : s() {}
    void push(int x) {
        if (s.size() == 0) {
            s.push(x);
            minx = x;
            return;
        }
        if (x >= minx) {
            s.push(x - minx);
        }
        else {
            s.push(x - minx);
            minx = x;
        }
    }

    int pop() {
        if (s.size() == 1) {
            s.pop();
            return minx;
        }
        int x = s.top();
        s.pop();
        if (x >= 0) {
            return minx + x;
        }
        else {
            int r = minx;
            minx -= x;
            return r;
        }
    }

    int min() {
        return minx;
    }
};

int main() {
    MinStack s;
    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int a, b;
        scanf("%d", &a);
        switch (a) {
        case 0:
            printf("%d\n", s.min());
            break;
        case 1:
            scanf("%d", &b);
            s.push(b);
            break;
        case 2:
            printf("%d\n", s.pop());
            break;
        }
    }
    return 0;
}