题目:
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示:
各函数的调用总次数不超过 20000 次
思路:
空间换时间。创建两个栈,一个数据栈,一个辅助栈。在辅助栈中存储数据栈中每个元素为栈顶时,数据栈的最小值。数据栈添加元素时,此时的数据栈最小值要么是当前添加的元素,要么是添加前的最小值。
代码:
class MinStack {//数据栈Stack data = new Stack<>();//辅助栈Stack mins = new Stack<>();/** initialize your data structure here. */public MinStack() {//初始化辅助栈mins.push(Integer.MAX_VALUE);}public void push(int x) {int min = mins.peek();if(x < min) {min = x;}data.push(x);mins.push(min);}public void pop() {data.pop();mins.pop();}public int top() {return data.peek();}public int min() {return mins.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();*/










