包含min函数的栈

包含min函数的栈

解法1:维护一个辅助栈,让辅助栈的栈顶始终是最小值

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        //如果添加的时候元素比辅助栈的栈顶元素小,就顺便也把元素添加到辅助栈
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        //如果弹出的是最小值,则把辅助栈的栈顶页弹出
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

解法2:如果当前压入的值比当前最小值,则压入一个当前最小值,再压入当前的值!

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private int min = Integer.MAX_VALUE;
    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int x) {
        //先压先前最小值
        //再压一个当前最小值,保证最小值一直存在
        if(x <= min){
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }
    
    public void pop() {
        if(stack.pop() == min){
            min = stack.pop();

         //如果相等一共弹出了俩次,不相等弹出一次
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return min;
    }
}

上一篇:包含min函数的栈


下一篇:《剑指Offer》包含min函数的栈(Java 实现)