最小栈 Min Stack

题目

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈

题目描述

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.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

思路&题解

默认栈的能力是后入先出，没有维护当前最小元素，因此问题的关键是如果保持栈的特性，同时能随时返回最小值。

由于栈可以入栈出栈，因此最小值必定不是一个整形的变量（是多个），我们需要在栈变化后任然能获取到最小值。一个思路是维护一个最小值的栈，每次入栈出栈，我们同步更新这个栈，保持栈大小相同，同时每次插入或者弹出新的最小值。

进一步的，我们可以把两个栈合并起来操作

class MinStack {

    /** initialize your data structure here. */
    private Stack<Integer> stack;
    public MinStack() {
        stack = new Stack<Integer>();
    }

    public void push(int x) {
        if(stack.isEmpty()){
            stack.push(x);
            stack.push(x);
        } else {
            int top = stack.peek();
            stack.push(x);
            stack.push(x>top?top:x);
        }
    }

    public void pop() {
        stack.pop();
        stack.pop();
    }

    public int top() {
        int top = stack.pop();
        int value = stack.pop();
        push(value);
        return value;
    }

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

知识点分析

本题重点是记录每次操作过程后的最小元素，由于对取最小元素有时间复杂度的要求：retrieving the minimum element in constant time。

取一个数，复杂度是常量级别，说明不能和问题的规模n挂钩，那只能是在栈变化的时候就记录下最小元素，同时需要用数组或者队列来保存每一个状态下的最小元素。 在Java中，栈的实现是Stack接口，可以用两个栈分别保存元素和最小元素。

进一步如果只用一个栈实现，需要对出栈和入栈做一下调整，合并两个栈为一个，本质是一个意思。

1. 入栈调整：每次入栈，需要同时将新元素和新栈的当前最小元素入栈，栈顶用于放最小元素
2. 出栈调整：每次出栈，需要连续出两次，将元素和最小元素都弹出
3. 取栈顶调整：每次取栈顶，需要先把最小元素弹出，然后再取元素，拿到元素后还需要把他再次入栈，这一步可以调用实现的入栈操作（一次入栈两个元素）。
4. 取最小值：获取栈顶的元素，即为最小值