设计一个有getMin功能的栈

1.题目

实现一个特殊的栈,在实现原有基本功能的基础上,加上返回栈中最小元素的操作

2.要求

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

  • 自己实现的栈可以使用现成的栈方法

3.解答

首先我的想法是每一次进行返回栈中最小元素的操作时,将栈中的元素全部pop出来到一个容器中,在这个过程中更新维护一个最小值,然后再把元素全部push会原来的栈中,这种方法虽然可以实现这个功能,但是这是一个非常狗屎的实现方式,首先,每次调用getMin()方法时都要重新创建一个容器,因为上一次方法调用的容易已经被上一次getMin()方法污染,其间可能进行若干次的push和pop操作,这样不能使用同一个数组,其次在进行返回最小值的过程中,要将全部元素来回折腾一遍,效率是非常低的,这种方法直接pass掉。

最终使用的方法是在栈进行具体的push和pop操作中,来维护这个最小值,在设计上我们使用两个栈,一个用来存放当前栈中的元素,和正常的栈没有区别,记为stackData,另一个用来记录这个过程中的最小值,记为stackMin。

  • 压入数据规则

假设当前数据为newData,首先将其压入到stackData中,然后判断stackMin是否为空:

如果stackMin为空,直接将newData压入栈中

如果不为空,那么判断newData和stackMin栈顶元素的大小:

​ 如果newData大于栈顶元素,那么继续执行下一步,continue

​ 如果newData小于或等于栈顶元素那么将其压入stackMin栈中

例如,在依次压入3,4,5,1,2,1的过程中,两个栈的情况:

image

  • 弹出数据规则

首先将stackData中的元素进行pop,得到value,和stackMin栈顶元素进行比较:

如果value大于stackMin栈顶元素,那么什么也不做

如果value等于栈顶元素,那么将stackMin栈顶元素也进行pop操作

根据前面压入数据规则我们可以直到,stackMin的栈顶元素不仅是stackMin中最小的,也是整个stackData中最小的,所以一定不会出现value小于stackMin栈顶元素的情况

最后,返回stackMin的栈顶元素,即使整个栈的最小元素

代码实现:

package java1;

import java.util.Stack;

/**
 * @Author : hadoo
 * @Date : 2020/3/16 21:27
 */
public class MyStack {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    public MyStack(){
        stackData = new Stack<>();
        stackMin = new Stack<>();
    }
    public void push(int newData){
        this.stackData.push(newData);
        if(this.stackMin.isEmpty())
            this.stackMin.push(newData);
        else if(newData <= this.getMin())
            this.stackMin.push(newData);
    }
    public int pop(){

        if(this.stackData.isEmpty()){
            throw new RuntimeException("Your stack is empty!!!");
        }
        int value = this.stackData.pop();
        if(value == this.getMin())
           this.stackMin.pop();
        return value;
    }
    public int getMin(){
        if(this.stackMin.isEmpty())
            throw new RuntimeException("your stack is empty!!!");
        return this.stackMin.peek();
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/设计一个有getmin功能的栈md