剑指Offer面试题：23.包含min函数的栈

一、题目
————————————————
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。
————————————————
二、思路
————————————————
思路：

要使时间复杂度是O（1），需要每次压入一个新元素进栈时，将栈里的所有元素排序，让最小的元素位于栈顶。但是这种想法不能保证最后压入栈的元素能够最先出栈，因为这个数据结构已经不是栈了。

于是借助于一个辅助的成员变量来存放最小的元素。每次压入一个新元素进栈的时候，如果该元素比当前最小的元素还要小，则更新最小元素，但是如果当前做小的元素被弹出栈了，怎么得到下一个最小元素是一个问题。分析到这里我们发现仅仅添加一个成员变量存放最小元素是不够的，也就是说当最小元素被弹出栈的时候，我们希望能够得到次小的元素。因此在压入最小元素之前，我们要把次小元素保存起来。故可以借助一个辅助栈把每次的最小元素都保存起来。
例子佐证：

————————————————
三、解决问题
————————————————
测试算例　

　　1.新压入数字更大

　　2.新压入数字最小

　　3.弹出数字最小

　　4.弹出数字不是最小
————————————————

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020-04-08 9:23
 */
import java.util.Stack;
/**
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。
 * 在该栈中，调用min、push及pop的时间复杂度都是O(1)。
 */

public class Solution23 {
    //存放元素栈
    Stack<Integer> dataStack = new Stack<Integer>();
    //辅助栈，data栈中每次进入一个元素，min辅助栈就存放当前data栈中的最小元素
    Stack<Integer> minStack = new Stack<Integer>();

    //data栈和min栈进入元素
    public void push(int node) {
        dataStack.push(node);
        //每次压入一个新元素进栈的时候，如果该元素比当前最小的元素还要小，则更新最小元素
        if(minStack.isEmpty() || node < minStack.peek()){
            minStack.push(node);
        }
        else{
            //如果该元素比当前最小的元素还要大或者等于，则添加辅助栈的栈顶元素
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

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

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

    public static void main(String[] args) {
        Solution23 demo = new Solution23();
        System.out.println("==============================");
        demo.push(3);
        System.out.println(demo.min());
        System.out.println("==============================");
        demo.push(4);
        System.out.println(demo.min());
        System.out.println("==============================");
        demo.push(2);
        System.out.println(demo.min());
        System.out.println("==============================");
        demo.push(1);
        System.out.println(demo.min());
        System.out.println("==============================");
        demo.pop();
        System.out.println(demo.min());
        System.out.println("==============================");
        demo.pop();
        System.out.println(demo.min());
        System.out.println("==============================");
        demo.push(0);
        System.out.println(demo.min());
        System.out.println("==============================");
    }
}

————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。