一. 题目

二. 思路

1. 堆+栈

• 堆维护最小值，栈维护栈顺序。

• 开栈对应堆和堆对应栈两个数组，维护关系。

2. 辅助栈

三. 代码

1. 堆+栈

class MinStack
{
    static final int N = (int) 3e4 + 10;
    int[] heap = new int[N], stk = new int[N];
    int[] sth = new int[N], hts = new int[N];//栈对应堆，堆对应栈
    int n, top;

    void swap(int[] a, int x, int y)
    {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    void heapSwap(int x, int y)
    {
        swap(heap, x, y);
        swap(sth, hts[x], hts[y]);
        swap(hts, x, y);
    }

    void up(int u)
    {
        while (u / 2 > 0 && heap[u / 2] > heap[u])
        {
            heapSwap(u / 2, u);
            u /= 2;
        }
    }

    void down(int u)
    {
        while (true)
        {
            int t = u;
            if (u * 2 <= n && heap[u * 2] < heap[t]) t = u * 2;
            if (u * 2 + 1 <= n && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
            if (t == u) break;
            heapSwap(t, u);
            u = t;
        }
    }

    public MinStack()
    {
        n = top = 0;
    }

    public void push(int val)
    {
        heap[++n] = stk[++top] = val;
        sth[top] = n;
        hts[n] = top;
        up(n);
    }

    public void pop()
    {
        int hp = sth[top--];
        heapSwap(hp, n--);
        up(hp);
        down(hp);
    }

    public int top()
    {
        return stk[top];
    }

    public int getMin()
    {
        return heap[1];
    }
}

2. 辅助栈

class MinStack
{
    static final int INF = Integer.MAX_VALUE;
    final Deque<Integer> stk = new ArrayDeque<>();
    final Deque<Integer> minStk = new ArrayDeque<>();

    public MinStack()
    {
        stk.clear();
        minStk.clear();
        minStk.offer(INF);
    }

    public void push(int val)
    {
        stk.offer(val);
        minStk.offer(Math.min(val, minStk.peekLast()));
    }

    public void pop()
    {
        stk.pollLast();
        minStk.pollLast();
    }

    public int top()
    {
        return stk.peekLast();
    }

    public int getMin()
    {
        return minStk.peekLast();
    }
}