【力扣学习计划】包含min函数的栈

最开始图省事,搞了一个list,在min函数被调用时将栈内现有数据全部排序后返回最小值

由于性能太差,考虑一个新的思路

设计思路:
由两个栈组成,A栈作为元素栈,B栈作为最小元素栈
push元素进栈时,和B栈栈顶元素比较,如果更小或相等则压入,否则不处理
pop元素出栈时,和B栈栈顶元素比较,如果相等则B栈也弹出元素
min方法直接返回B栈栈顶元素即可

--解答错误
在执行push时,如果相等元素再次压入,需要在B栈也做压入处理,防止A栈有多个最小元素,弹出一个后B栈为空,导致结果出错

class MinStack {

    Stack<Integer> a = null;
    Stack<Integer> b = null;

    /** initialize your data structure here. */
    public MinStack() {
        a = new Stack<>();
        b = new Stack<>();        
    }
    
    public void push(int x) {
        a.push(x);
        if (b.isEmpty() || b.peek() >= x) {
            b.push(x);
        }
    }
    
    public void pop() {
        if (!b.isEmpty() && b.peek().equals(a.pop())) {
            b.pop();
        }
    }
    
    public int top() {
        return a.peek();
    }
    
    public int min() {
        if (b.isEmpty()) {
            return a.peek();
        } else {
            return b.peek();
        }
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

 

上一篇:【无标题】


下一篇:有效括号-栈