设计一个有getMin功能的栈

题目

• 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

要求

• pop、push、getMin操作的时间复杂度都是O(1)
• 设计栈类型可以使用现成的栈结构

分析

不知道有没有一开始想法跟我一样的。用一个数保存最小值就可以了啊？但是实际上不是的，如果这样设计当你最小值出栈的时候怎么办呢？实际上，我们可以用两个栈来实现，一个用于存储栈的值，另外一个用于存储最小值序列。

push函数

如果push时min栈为空，那么这个值肯定是最小值、直接放入空栈即可。如果不为空，但是这个值比当前min栈中栈顶的值小，那么也需要入栈，否则不入min栈。

代码如下:

/*这里是入栈操作*/
    public void push(int num){
        if (stackMin.isEmpty()){
            stackMin.push(num);
        }else if (num <= stackMin.peek()){
            stackMin.push(num);
        }
        stackData.push(num);
    }

pop函数

要想出栈，首先要检查当前栈是否为空，如果为空则直接抛出异常。如果不为空，那么需要去看min栈顶是否与要存储值的栈栈顶相等，如果相等min栈顶则需要出栈。

代码如下：

/*这里是出栈操作*/
    public int pop(){
        if (stackData.isEmpty()){
            throw new RuntimeException("栈空!");
        }
        int value = stackData.pop();
        if (stackMin.peek() == value){
            stackMin.pop();
        }
        return value;
    }

getMin函数

如果min栈空，则抛出异常，否则，返回min栈顶元素。

代码如下:

/*这里是返回最小值函数*/
    public int getMin(){
        if (stackMin.isEmpty()){
            throw new RuntimeException("栈空，无最小值");
        }
        return stackMin.peek();
    }

完整代码如下:

package stack_queue;
import java.util.Stack;

public class GetMinStack {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    public GetMinStack(){
        stackData = new Stack<>();
        stackMin = new Stack<>();
    }
    /*这里是入栈操作*/
    public void push(int num){
        if (stackMin.isEmpty()){
            stackMin.push(num);
        }else if (num <= stackMin.peek()){
            stackMin.push(num);
        }
        stackData.push(num);
    }
    /*这里是出栈操作*/
    public int pop(){
        if (stackData.isEmpty()){
            throw new RuntimeException("栈空!");
        }
        int value = stackData.pop();
        if (stackMin.peek() == value){
            stackMin.pop();
        }
        return value;
    }
    /*这里是返回最小值函数*/
    public int getMin(){
        if (stackMin.isEmpty()){
            throw new RuntimeException("栈空，无最小值");
        }
        return stackMin.peek();
    }
}