题目
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
• push(x) -- 将元素 x 推入栈中。
• pop() -- 删除栈顶的元素。
• top() -- 获取栈顶元素。
• getMin() -- 检索栈中的最小元素。
示例
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
思路
请参考设计一getMin的栈
代码演示
package com.itz.stackAndQueue;
import java.util.Stack;
/**
* 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
* <p>
* push(x) -- 将元素 x 推入栈中。
* pop() -- 删除栈顶的元素。
* top() -- 获取栈顶元素。
* getMin() -- 检索栈中的最小元素。
* 示例:
* <p>
* MinStack minStack = new MinStack();
* minStack.push(-2);
* minStack.push(0);
* minStack.push(-3);
* minStack.getMin(); --> 返回 -3.
* minStack.pop();
* minStack.top(); --> 返回 0.
* minStack.getMin(); --> 返回 -2.
* <p>
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/min-stack
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/**
* 执行用时 :
* 8 ms
* , 在所有 java 提交中击败了
* 100.00%
* 的用户
* 内存消耗 :
* 40.2 MB
* , 在所有 java 提交中击败了
* 95.58%
* 的用户
*/
public class MinStack {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
/**
* initialize your data structure here.
*/
public MinStack() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
public void push(int x) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(x);
} else if (x <= this.getMin()) {
this.stackMin.push(x);
}
this.stackData.push(x);
}
public void pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("你没有添加数据");
}
if (stackData.pop() == this.getMin()) {
this.stackMin.pop();
}
}
public int top() {
return stackData.peek();
}
public int getMin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("你没有添加数据");
}
return this.stackMin.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.getMin();
*/
总结：
本题有两种方案设计一getMin的栈 两种方案的时间复杂度和空间复杂度都分别是O(1)、O(n)，只是方法一：在压入的时候稍微省空间、但弹出的时候稍微费时间，方案二 在压入的时候稍微费空间、但弹出的时候稍微省时间。
