最开始图省事,搞了一个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(); */