题目描述

blablabla

样例

blablabla

算法1

(辅助栈，同时压栈) $O(n)$

分三种方法
1、（基础）x入栈，然后辅助栈的栈顶和x比较，x小，将x压入辅助栈，栈顶小，将栈顶压入
2、（中级）x入栈，然后辅助栈的栈顶和x比较，x小，将x压入辅助栈，栈顶小，不压入，pop时，x与栈顶比较，如果相同，同时弹栈，但如果一直是相同的最小值，会一直push辅助栈
3、（高级）x入栈，然后辅助栈的栈顶和x比较，x小，将x的索引压入辅助栈，栈顶小，不压入，pop时，x与栈顶比较，如果索引相同，同时弹栈。
只放基础代码

Java 代码

class MinStack {

    /** initialize your data structure here. */
    Stack<Integer> stack;
    Stack<Integer> min;
    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(min.empty()){
            min.push(x);
        }else{
            Integer minNum = min.peek();
            if(x<=minNum){
                min.push(x);
            }else{
                min.push(minNum);
            }
        }
    }

    public void pop() {
        stack.pop();
        min.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min.peek();
    }
}