题解 | #包含min函数的栈#

描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数及 pop函数的时间复杂度都是 O(1)
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
示例:
输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出: -1,2,1,-1
解析:
"PSH-1"表示将-1压入栈中，栈中元素为-1
"PSH2"表示将2压入栈中，栈中元素为2，-1
“MIN”表示获取此时栈中最小元素==>返回-1
"TOP"表示获取栈顶元素==>返回2
"POP"表示弹出栈顶元素，弹出2，栈中元素为-1
"PSH-1"表示将1压入栈中，栈中元素为1，-1
"TOP"表示获取栈顶元素==>返回1
“MIN”表示获取此时栈中最小元素==>返回-1

解法一：利用辅助栈

根据栈的性质很容易得知push函数及 pop函数的时间复杂度都是 O(1)，但min函数时间复杂度明显不为O(1)，最容易思考的方法则为创建一个辅助栈，即利用空间换时间，思路如下：

创建一个辅助栈，为后续取栈中最小值做准备
push方法构建：先将元素压入原栈内，若辅助栈为空或者辅助栈栈顶元素>该元素值，则将该元素放入辅助栈，否则辅助栈中压入上次栈顶元素（这样即可保持辅助栈栈顶元素一直为最小值）
pop时将原栈及辅助栈中栈顶元素均pop即可，这样即可保持原栈及辅助栈元素个数一致
top时只需要获取原栈中top元素
min时从辅助栈获取top元素即可

push方法简易图解：
图片说明

代码如下：

   //创建原栈及辅助栈
    private Stack<Integer> originalData = new Stack<Integer>();
    private Stack<Integer> minData = new Stack<Integer>();

    public void push(int node) {
        originalData.push(node);
        if(minData.isEmpty() || node <= minData.peek()){ //
            minData.push(node);
        }else{
            minData.push(minData.peek());//当压入的结点大时，则每次都压入min栈顶的值。 
        }    
    }

    public void pop() {
        originalData.pop();//出栈时，min栈和data栈均出栈
        minData.pop();
    }

    public int top() {
        return originalData.peek();
    }

    public int min() {
        return minData.peek();
    }

时间复杂度：O(1)
空间复杂度：因为利用了辅助栈，空间复杂度O(n)

解法二：压缩转换法

由方法一很容易得知辅助栈存储的即为最小值，我们可利用该性质构建一个变量min，并将其放入栈中，最后即可得到一个栈及冗余变量min
简单图解如下：
图片说明

由上面两图思想可得代码如下：

    private Stack<Integer> stack = new Stack<Integer>();
    private int min = 0;
    public void push(int node) {
        if(stack.isEmpty()){
            min = node; //栈为空时，将min值赋值为node
        }
        stack.push(node-min); //将node-min的差值即diff放入栈中
        if(min>node){
            min = node; //保证min值为node元素最小值
        }
    }

    public void pop() {
      if(!stack.isEmpty()){
            int val = stack.pop();
            if(val<0){
                min = min-val; //若差值小于0，则说明出栈元素是当前最小值min，则需将min跟新为前一个最小值
            }  
        }
    }

    public int top() {
      int val = stack.peek();
        if(val<0){  //若diff小于0，则value为min值，否则，value值为min+val
            return min;
        }else{
            return min+val;
        }
    }

    public int min() {
      return min;
    }

时间复杂度：O(1)
空间复杂度：额外空间复杂度为O(1)