没错，我就是来搞笑的

算法1

(线段树) $O(nlogn)$

C++ 代码

class MinStack {
public:
    /** initialize your data structure here. */
    struct Tree {
        struct {
            int l, r;
            long long dat;
        } t[1000000 * 4];

        void build(int p, int l, int r) {
            t[p].l = l, t[p].r = r;
            if (l == r) {
                t[p].dat = 1e12;
                return;
            }
            int mid = (l + r) >> 1;
            build(p << 1, l, mid);
            build(p << 1 | 1, mid + 1, r);
            t[p].dat = 1e12;
        }

        void change(int p, int x, long long v) {
            if (t[p].l == t[p].r) {
                t[p].dat = v;
                return;
            }
            int mid = (t[p].l + t[p].r) >> 1;
            if (x <= mid)change(p << 1, x, v);
            else change(p << 1 | 1, x, v);
            t[p].dat = min(t[p << 1].dat, t[p << 1 | 1].dat);
        }

        long long ask(int p, int l, int r) {
            if (l <= t[p].l && r >= t[p].r)return t[p].dat;
            int mid = (t[p].l + t[p].r) >> 1;
            long long val = 1e12;
            if (l <= mid)val = min(val, ask(p << 1, l, r));
            if (r > mid)val = min(val, ask(p << 1 | 1, l, r));
            return val;
        }
    }tr;
    stack<int>s;
    int tot=0;
    MinStack() {
        tr.build(1,1,1000000);
    }

    void push(int x) {
        tot++,tr.change(1,tot,x);
        s.push(x);
    }

    void pop() {
        tr.change(1,tot,1e12),tot--;
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return tr.ask(1,1,tot);
    }
};