LintCode 12. Min Stack 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/min-stack/
Implement a stack with min() function, which will return the smallest number in the stack.
It should support push, pop and min operation all in O(1) cost.
Notice
min operation will never be called if there is no number in the stack.
Example
push(1)
pop() // return 1
push(2)
push(3)
min() // return 2
push(1)
min() // return 1
解题思路
题目是建一个能以O(1)时间查找栈中最小数的栈。
- 此题只需额外地建一个Stack来额外记录当前栈中的最小数即可。
参考代码
public class MinStack {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MinStack() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int number) {
stack1.push(number);
if (!stack2.isEmpty()) {
stack2.push(Math.min(stack2.peek(), number));
} else {
stack2.push(number);
}
}
public int pop() {
if (stack1.isEmpty()) {
throw new NoSuchElementException();
}
stack2.pop();
return stack1.pop();
}
public int min() {
return stack2.peek();
}
}