题目描述

解题思路

辅助栈

和此题一样https://www.yuque.com/jugelizi-rxt6d/dqbihl/iac9ha。
但也可以写成这样：
每次放入栈，同步的把最小值放入，就算重复也放入，注意同步！！！

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
        minStack.push(Integer.MAX_VALUE);
    }
    public void push(int val) {
        stack.push(val);
        // 比较放入最小的值
        minStack.push(Math.min(minStack.peek(), val));
    }
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

差值法

使用了1个辅助栈，保存最小值，怎么可以实现不使用额外的空间呢？
栈保存差值，而使用一个变量来记录最小值，但需要注意出栈的时候，出栈需要对差值进行判断，如果diff小于0，那么min需要更新，大于0也需要更新。

/**
     * stack用来存储和min的差值，min存储最小值，每次出栈的时候通过差值和当前min计算要出栈的值和之前的min
     * 如果差值diff大于等于0，说明要出栈的值大于等于当前min，那么要出栈的值在入栈的时候没有更新min，返回min+diff；
     * 如果差值diff小于0，说明当前要出栈的值就是min(因为入栈的时候我们选择的就是min和入栈元素的最小值)，同时，通过min-diff计算出之前min
     * 要注意的是diff可能会超出int范围，类似于 Integer.MAX_VALUE - 1 这种，所以diff要用Long存
     */
class MinStack {
    Integer min = null;
    Stack<Long> stack;   // 保存差值，使用Long，防止越界
    public MinStack() {
        stack = new Stack<>();
    }
    public void push(int val) {
        if (stack.isEmpty()) {
            // 第一个数min=x,差值为0
            stack.push(0L);
            min = val;
        }else {
            stack.push(Long.valueOf(val) - min);
            min = Math.min(val, min);
        }
    }
    public void pop() {
        Long diff = stack.pop();
        if (diff < 0) {
            // 如果弹栈的小于min，那须需要把差值加上去，因为在放入的时候
            min = (int)(min - diff);
        }
    }
    public int top() {
        Long diff = stack.peek();
        if (diff >= 0) {
            return (int) (diff + min);
        }else {
            return min;
        }
    }
    public int getMin() {
        return min;
    }
}