最小(大)栈--双栈单栈两种解法

最小(大)栈

标明：以下代码为最小栈讲解，求最大栈只需将入栈判断条件做以修改即可。

题目描述：

设计一个支持 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.

题目解析：

我们通过解析题目可以知道，该题实际上是要求我们自定义一个栈，实现简单的入栈、出栈、弹出最顶层元素三个基础功能。最核心的是要实现返回最小栈元素(要求时间复杂度在常数范围内，即O(常数))。

两种解题思路：

针对于题目对时间复杂度的要求，我们可有以下两种解题思路：

1.双栈思路。因题目只对时间复杂度有要求，而对空间复杂度无要求。因此我们可以创建两个栈，一个栈用于存储实际数据，另一个栈用于存储最小元素，getMin()方法只需直接返回存储最小元素栈的最顶层元素即可。

双栈思路时间复杂度为O(1)，空间复杂度为O(n)。

2.单栈思路。假设该题对时间复杂度和空间复杂度都要求为O(1)时，我们就可使用该方法实现。单栈顾名思义就是只创建一个栈，我们进行入栈操作时可push()两次，第一次为实际数据，第二次为最小元素(即每个实际数据后面均跟着最小元素)，getMin()方法只需直接返回栈顶元素即可。

双栈思路和单栈思路图解：

双栈思路：

单栈思路：

双栈思路实现代码：

import java.util.Stack; class MinStack { //创建dataStack栈存放实际元素 private Stack<Integer> dataStack; //创建minDataStack栈存放最小元素 private Stack<Integer> minDataStack; /** initialize your data structure here. */ public MinStack() { dataStack=new Stack<>(); minDataStack=new Stack<>(); } //入栈 public void push(int x) { //当minDataStack栈为空或入栈数据小于或等于该栈栈顶元素时入栈 //将<=改为>=即可dataStack栈中存储的为最大元素 if(minDataStack.isEmpty()||x<=minDataStack.peek()){ minDataStack.push(x); } //dataStack栈存放实际元素，无论如何都会入栈 dataStack.push(x); } //出栈 public void pop() { //如果存放实际元素栈要出栈元素与minDataStack栈顶元素相等，则minDataStack栈顶元素也需出队，若不相等则只需dataStack栈顶元素出队即可 //为什么minDataStack栈顶元素若与dataStack元素出栈元素相等，minDataStack栈顶元素也要出栈呢？原因是minDataStack栈顶存放的是最小元素，若dataStack要出栈元素与最小元素相同则表明dataStack要出栈元素即为栈内最小元素，出栈后最小元素将更新，故minDataStack栈顶元素也要出栈，否则minStack已经更新了最小元素，而minDataStack内最小元素还为旧值 //此处Stack创建为包装类Integer，包装类比较内容相等时需用equals方法，==比较的是指向堆内存的地址是否相等 if(dataStack.peek().equals(minDataStack.peek())){ minDataStack.pop(); } //无论如何调用一次pop()方法存放实际元素的栈需要出栈栈顶元素 dataStack.pop(); } public int top() { //返回存放数据的栈的栈顶元素 return dataStack.peek(); } public int getMin() { //返回存放最小元素栈的栈顶元素即可 return minDataStack.peek(); } } public class Main{ public static void main(String[] args) { MinStack stackTest=new MinStack(); stackTest.push(1); stackTest.push(2); stackTest.push(3); System.out.println(stackTest.top()); stackTest.pop(); System.out.println(stackTest.getMin()); } } /** 3 1 **/

单栈思路：

import java.util.Stack; //最小(大)栈 //单栈--->push两次，实际数据后面跟最小元素 class MinStack{ private Stack<Integer> stack; public MinStack() { stack=new Stack<>(); } public void push(int x){ //当栈为空时，第一个入栈的元素也为最小元素 if(stack.isEmpty()){ stack.push(x); stack.push(x); }else {//当栈内存在元素时 int temp=stack.peek();//将当前最小元素暂存 stack.push(x);//将实际元素入栈 //将新入栈元素与当前最小元素比较 if(x<=temp){//若小于等于更新最小值将<=改为>=即可dataStack栈中存储的为最大元素 stack.push(x); }else {//若大于则依旧将最小值入栈 stack.push(temp); } } } public void pop(){ if(stack.isEmpty()){ System.out.println("当前栈为空"); return; } //删除两次即可 stack.pop(); stack.pop(); } //弹出栈顶元素 //我们知道栈顶元素为最小值，不一定是实际最后一个入栈的元素，故弹出栈顶元素我们需要先将最小元素出栈保存，然后返回实际栈顶元素，最后再将最小元素入栈 public int top(){ if(stack.isEmpty()){ System.out.println("当前栈为空"); } int result=stack.pop(); int data=stack.peek(); stack.push(result); return data; } //最小值为栈顶元素 public int getMin(){ return stack.peek(); } } public class Main{ public static void main(String[] args) { MinStack stackTest=new MinStack(); stackTest.push(1); stackTest.push(2); stackTest.push(3); System.out.println(stackTest.top()); stackTest.pop(); System.out.println(stackTest.getMin()); } } /** 3 1 **/