155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

这是一道关于栈的经典题目，要求任何时候都能从栈中取得当前栈内元素中的最小值（也可变种为最大值）。

解法一

是维护一个维护最小值的栈minStack，每次push元素X的时候，将X与minStack[top]进行比较，将较小的值push进minStack，pop元素时，minStack也同时pop。这样时间复杂度是O(1)，空间复杂度是O(2*N)，N为栈内元素，缺点是需要用到两个栈。

解法二

能否只用一个栈来实现？可以！

在解法一中，有两点需要注意：

任何时候只是minStack的peek元素是有用的，其他元素实际上是备用的状态。
当最小元素min连续n次不变时，minStack会有连续n个m，什么时候min会变为一个更小的值呢？当新来的X比当前最小值min更小的时候，也就是在此时，min的值发生了变化。

因此，如果我们可以做两件事，一是用变量min记录当前栈内最小值，二是将这个min值发生变化的‘事件’记录下来，就可以减少对栈空间的使用。

如何记录min值发生变化的‘事件’呢，可以在元素X入栈前，看一下元素X的入栈是否会导致min变小（注意这里要包含相等的情况），即if(X<=min)，如果会，就把min变化前的值先入栈，再入栈X，这样等X出栈的时候，X就是出栈时的栈内元素的最小值，这时我们再pop一次把X入栈前的最小值取出赋予min。

前面说到‘要包含相等的情况’，为什么？因为我们需要知道在出栈时X自己是否就是最小值，即if(X==min)，如果是，说明X入栈时，min发生了变化。

代码如下：

class MinStack {
    private int min;
    private Stack<Integer> stack;
    public MinStack() {
        stack = new Stack<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        if (x <= min) {
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {
        if (stack.pop() == min) {
            min = stack.pop();
        }
    }

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

    public int getMin() {
        return min;
    }
}

最后编辑于：2020.06.20 19:45:20