算法---栈的最小值

实现一个这样的栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值。栈里面存放的都是 int 整数，并且数值的范围是 [-100000, 100000]。要求所有操作的时间复杂度是 O(1)。附加：如果空间复杂度也能O(1)的话可加分。

一、时间 O(1) + 空间 O(n)
这个要求其实也不难，我们可以用一个辅助栈来存放最小值。例如我们有两个栈 stack 和 helper，stack 是目标栈，helper 是辅助栈，用来存放最小值。每次 getMin 的时候，直接从 helper 栈顶获取即可。下面重点讲一下 push 操作。

每次进行 push 操作的时候，进行如下操作（假设要 push 的元素是 t）

1、对于 stack 栈，我们按照正常情况把元素 push 到栈顶就可以了。

2、然后要把元素 t push 到 helper 栈顶的时候，要先把 t 与 helper 栈顶的元素（假设是 a）进行比较，如果 t <= a，则把元素 t push 到 helper 的栈顶，如果 t > a，这个时候，我们不把 t push 进去，而是重复把 a push 到 helper 的栈顶。

我举个例子吧，例如我们要把数组 arr = {2, 1, 3} 都放入栈中，则存放过程如下：

1、首先 push 2。由于刚开始 stack 和 helper 都是空的，所以直接把 2 放入，此时目标栈和辅助栈的值如下：stack = {2}，helper = {2}。

2、接下来 push 1。由于 helper 栈顶元素比 1 大，所以直接把 1 放入 helper 的栈顶，此时：stack = {2, 1}，helper = {2, 1}。

3、接下来 push 3，由于 helper 栈顶元素比 3 小，所以重复把 栈顶的元素再次入栈，此时：stack = {2, 1, 3}，helper = {2, 1, 1}。

对于 pop 操作，直接把两个栈的栈顶元素删除即可，所以具体代码如下：
 

public class MinValStack {
    private static Stack<Integer> stack = new Stack<>();
    private static Stack<Integer> helper = new Stack<>();

    public static void push(Integer data) {
        stack.push(data);
        if (helper.isEmpty() || data < helper.peek()) {
            helper.push(data);
        } else {
            helper.push(helper.peek());
        }
    }

    public static Integer pop() {
        if (stack.isEmpty()) {
            return null;
        }
        helper.pop();
        return stack.pop();
    }

    public static Integer getMin() {
        return helper.isEmpty() ? null : helper.peek();
    }

}

二、时间 O(1) + 空间 O(1) 

这种方法的话，我们的 stack 栈中，不能存放原始数值，而是应该存放 差值，啥差值？就是存放栈顶与最小值的差值。我还是详细一点给大家讲一个案例吧，案例配合代码，应该还是挺好理解的，例如 arr = {2, 1, 3, 0}，那么把这些元素入栈时，stack 栈中元素以及最小值的变化如下

上面表格是 push 时，栈中数值的变化，然后再进行 getMin 和 pop 可以通过相应的判断获取，直接看我的代码实现吧，我会进行相应解释，挺好懂，代码如下：

注意：少了一行代码

pop方法里当top<=0时：

if(top<=0){

int result=min;

min=min+compare;

 return result;

}
 

public class MinValStackBestSolution {
    private static Stack<Integer> stack = new Stack<>();
    private int min;

    public void push(int data) {
        if (stack.isEmpty()) {
            min = data;
            stack.push(0);
        } else {
            int compare = data - min;
            stack.push(compare); //存放和最小值的差值
            min = compare < 0 ? data : min;
        }
    }

    public int pop() {
        int top = stack.pop();
        if (top <= 0) { //如果栈顶元素<0,返回最小值min
            return min;
        } else {//如果栈顶元素>0,返回min+top
            return min + top;
        }
    }

    public int getMin() {
        return min;
    }

}