题目描述

题目描述
请设计一个栈结构，支持 push、pop、top以及getMin操作，且每个操作的时间复杂度都是 O(1)O(1)。

push(x) – 向栈中压入元素 xx；
pop() – 删除栈顶元素；
top() – 返回栈顶元素；
getMin() – 返回栈中的最小元素

样例

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

算法

(栈) $O(1)$

这个方法只用了一个栈，并使用了一个常数min来记录当前最小值。当push的值x小于当前的最小值min，将min和x先后push，并更新当前的min = x; 当pop的值等于当前最小值min，进行两次pop操作，并更新当前最小值。

时间复杂度分析：四种操作都是O(1)时间的常数项入栈出栈操作；

JAVA 代码

class MinStack {

    Stack<Integer> stk = new Stack<Integer>();
    int min = Integer.MAX_VALUE;
    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        // 当 x 小于当前最小值 min， 将 min 和 x 先后push到stack里， 并更新此时的最小值 min = x
        if (x <= min) {
            stk.push(min);
            min = x;
        }
        stk.push(x);

    }

    public void pop() {
        // 当pop的值等于当前最小值 min， 多进行一次pop操作，并更新此时的最小值
        if (stk.pop() == min)
            min = stk.pop();
    }

    public int top() {
        return stk.peek();

    }

    public int getMin() {
        return min;

    }
}