包含min函数的栈题解

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

28

题目:

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 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();*/