栈之包含min函数的栈

1.本题知识点

   栈

2. 题目描述

   定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

3. 思路

   此题需要借助辅助栈，存储最小值，具体过程看图解：

   如上图， 每次压入数据栈时，需要比较辅助栈中最小值(末尾元素)的大小，小的话追加到辅助栈末尾，否则再复制一份最小值追加到辅助栈末尾。

   Java版本：

import java.util.Stack;

public class Solution {
    private Stack<Integer> s_data = new Stack<>();  //数据栈
    private Stack<Integer> s_assist = new Stack<>();//辅助栈
    
    public void push(int node) {
        s_data.push(node);//数据栈压入
        //注意：辅助栈只存储每次比较的较小数值，如果新加元素较大，辅助栈再存一遍最小值。看图解
        //如果辅助栈为空，或者当前数值小于辅助栈
        if(s_assist.isEmpty() || node < s_assist.lastElement()){
            s_assist.push(node);//辅助栈压入当前数值
        }
        else{
            s_assist.push(s_assist.lastElement());//辅助栈压入辅助栈末尾的最小数值
        }
    }
    
    public void pop() {
    	//数据栈和辅助栈的数据量 必须保持一致
        if(!s_data.isEmpty() && !s_assist.isEmpty()){
            s_data.pop();
            s_assist.pop();
        }
    }
    
    public int top() {
        return s_data.firstElement();
    }
    
    public int min() {
        //最小值为辅助栈末尾元素
        return s_assist.lastElement();
    }
}