题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素min的函数。在该栈中，min、push、pop的时间复杂度都是O(1)
解题思路:
- 定义两个栈，stack用于存储正常的栈元素，一个辅助栈minStack，用于保存最小值。
- 当数据data入栈的时候，比较data和minStack栈顶元素的大小，将两者的最小值入栈minStack。minStack的栈顶元素就是栈的最小值。
- 获取最小值的时候，只需返回minStack的栈顶元素即可。
代码
static class StackWithMin {
private Stack<Integer> stack = new Stack<>();
private Stack<Integer> min = new Stack<>();
public void push(int data){
stack.push(data);
if (min.isEmpty()) {
min.push(data);
} else {
min.push(data < min.peek() ? data : min.peek());
}
}
public int pop(){
if (stack.isEmpty()) {
throw new RuntimeException("empty stack!!");
}
min.pop();
return stack.pop();
}
public int min(){
if (stack.isEmpty()) {
throw new RuntimeException("empty stack!!");
}
return min.peek();
}
}
