题解 | #设计getMin功能的栈#

设计getMin功能的栈

https://www.nowcoder.com/practice/05e57ce2cd8e4a1eae8c3b0a7e9886be

1.设计一个有getMin功能的栈

问题描述：

实现一个特殊栈，在实现栈的基本功能的基础上能够以O(1)返回栈中最小元素

要求：

pop、push、getMin操作的时间复杂度都是O(1)

能用现成的栈结构

难度：1星

解题方法

使用两个栈，一个栈存真正放在栈中的元素(stackData)，一个栈放每一步下栈中当前状态的最小值(stackMin)

设计方案1

（1）压入数据

直接压入stackData，然后是关于stackMin的压入，有两种情况：

stackMin为空，直接压入
stacjMin不为空，比较待压入元素和stackMin栈顶元素、
- 待压入元素小/相等，压入
- 待压入元素大，不压入

图例：

（2）弹出数据

stackData中直接弹出栈顶元素，记为value，拿value和stackMin中的元素比较

value等于stackMin中的栈顶元素弹出
value大于stackMin中的栈顶元素不弹出
不可能出现小于的情况，因为stackMin栈顶的元素就是当前stackData栈中所有元素的最小值

（3）查询当前栈中最小值

stackMin栈的栈顶元素即为当前栈中的最小值

代码如下：

class MinStack {     private Stack<Integer> stackData;     private Stack<Integer> stackMin;     /** initialize your data structure here. */     public MinStack() {         stackData = new Stack<Integer>();         stackMin = new Stack<Integer>();     }          public void push(int x) {         stackData.push(x);         if(stackMin.isEmpty()) {             stackMin.push(x);         } else {             if(stackMin.peek() >= x) {                 stackMin.push(x);             }         }     }          public void pop() {         int value = stackData.pop();         if(value == stackMin.peek()) stackMin.pop();     }          public int top() {         return stackData.peek();     }          public int getMin() {         return stackMin.peek();     } }

设计方案2

方案一两个栈中的元素其实不是一一对应的，也就是说在某个状态下两个栈中的元素数量不一，那么在进行弹出操作时需要进行判断。

方案二和方案一不同的点在于方案二两个栈元素对应，弹出时无需判断，但是压入时压入的元素比方案一多

（1）压入数据

stackData直接压入，stackMin分为如下情况

stackMin为空：直接压入
stackMin不为空：
- 待压入元素大于stackMin栈顶元素，则压入当前栈顶元素
- 待压入元素小于等于stackMin栈顶元素，则压入待压入元素

（2）弹出数据

两个栈直接弹出即可

（3）查询当前栈中最小值

当前栈中的最小值为stackMin栈的栈顶元素

代码如下：

class MinStack {     private Stack<Integer> stackData;     private Stack<Integer> stackMin;     /** initialize your data structure here. */     public MinStack() {         stackData = new Stack<Integer>();         stackMin = new Stack<Integer>();     }          public void push(int x) {         stackData.push(x);         if(stackMin.isEmpty()) {             stackMin.push(x);         } else {             if(stackMin.peek() >= x) {                 stackMin.push(x);             } else {                 stackMin.push(stackMin.peek());             }         }     }          public void pop() {       stackData.pop();       stackMin.pop();     }          public int top() {         return stackData.peek();     }          public int getMin() {         return stackMin.peek();     } }