力扣
https://leetcode-cn.com/problems/min-stack/
难度简单1041
设计一个支持?
push?，pop?，top?操作，并能在常数时间内检索到最小元素的栈。
push(x)?—— 将元素 x 推入栈中。pop()?—— 删除栈顶的元素。top()?—— 获取栈顶元素。getMin()?—— 检索栈中的最小元素。示例:
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.提示：
pop、top?和?getMin?操作总是在?非空栈?上调用。通过次数287,899提交次数502,228
题目描述：
设计一个支持push，pop，top的操作，并能够在常数时间内检索到最小元素的栈。
- push(x)，——将元素x压入栈中；
- pop()，——删除栈顶元素；
- top()，——获取栈顶元素；
- getMin(),——获取栈中的最小元素。
示例：
解释：
先创建一个栈——minStack；
然后push进栈一个元素-2，
然后push进栈一个元素0，
然后push进栈一个元素-3，
然后获取栈中的最小元素——返回-3，
然后进行pop出栈栈顶元素-3，
然后top获取栈顶元素——返回0，
然后获取栈中的最小元素——返回-2。
使用现有的栈数据结构可以完成pop、push、top（对应的是peek操作），但是无法在常数时间内完成getMin()操作，我们的办法是使用一个辅助栈来辅助完成操作。
如下图所示：
?举例：
- 首先创建一个数据栈，和一个辅助栈。
- 然后push进栈一个元素-2，因为当前数据栈和辅助栈都是空的，所以直接push进去。
- 然后push进栈一个元素0，因为0>-2，所以辅助栈的栈顶元素仍然是-2；
- 然后push进栈一个元素-3，因为-3小于当前栈顶元素-2，所以-3成为新的栈顶元素；
- 然后执行getMin操作，获取当前最小元素，也就是当前辅助栈的栈顶元素——-3；
- 然后执行pop出栈操作，因为辅助栈的栈顶元素和数据栈要出栈的元素一样，所以数据栈和辅助栈都执行出栈操作；
- 然后执行top操作，返回当前数据栈的栈顶元素，即0；
- 然后执行getMin操作，返回当前辅助栈的栈顶元素，即-2。
代码：
package zyh.springcloud.chapter2.service.impl.datastructure.stack;
import java.util.Deque;
import java.util.LinkedList;
/**
* @ClassName minStack
* @Author zhangyonghui
* @Description：最小栈
* @Date 2021/10/2 16:59
* @Version 1.0
**/
public class MinStack {
private Deque<Integer> dataStack;
private Deque<Integer> fuzhuStack;
/**
* 思想：使用一个辅助栈进行操作：（始终将数据栈栈中最小的元素存入辅助栈的栈顶）
* 1，当进行入栈的时候，将进行入栈的元素与辅助栈中的栈顶元素进行比较，如果小于当前辅助栈中的栈顶元素，则将该最小值也压入辅助栈中，成为新的栈顶元素；
* 2，当进行出栈的时候，如果出的元素同时也是辅助栈的栈顶元素，那么连同辅助栈进行一起出栈；
* 3，当获取栈中的最小元素的时候，则获取辅助栈的栈顶元素。
*/
/**
* 构造方法：初始化一个数据栈、一个辅助栈；
*/
public MinStack() {
dataStack = new LinkedList<>();
fuzhuStack = new LinkedList<>();
}
/**
* 入栈操作：进行入栈操作的时候，比较即将入栈的元素与辅助栈中的栈顶元素，如果小于，则将该入栈的元素同时也压入到辅助栈中，成为新的栈顶元素；
* @param val
*/
public void push(int val) {
//如果辅助栈是空的，则不需要进行比较，直接入栈：
if (fuzhuStack.isEmpty()) {
dataStack.push(val);
fuzhuStack.push(val);
}
//如果辅助栈是非空的，则进行比较：
else{
//取出辅助栈中的现在的栈顶元素：
Integer nowStackDing = fuzhuStack.peek();
//进行比较：
if (nowStackDing >= val) {
//将该val压入辅助栈，成为新的栈顶元素；
fuzhuStack.push(val);
}
//压入数据栈：
dataStack.push(val);
}
}
public void pop() {
//出栈操作：如果该数据栈的栈顶元素同时也是辅助栈的栈顶元素，则同时进行出栈，否则只进行数据栈的出栈操作；
if (dataStack.peek().equals(fuzhuStack.peek())) {
dataStack.pop();
fuzhuStack.pop();
}else {
dataStack.pop();
}
}
public int top() {
//获取栈顶元素：
if (!dataStack.isEmpty()) {
return dataStack.peek();
}else{
return -1;
}
}
//获取最小值：
public int getMin() {
if (!fuzhuStack.isEmpty()) {
return fuzhuStack.peek();
}else {
return -1;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
}