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:

    1. MinStack minStack = new MinStack();
    2. minStack.push(-2);
    3. minStack.push(0);
    4. minStack.push(-3);
    5. minStack.getMin();   --> Returns -3.
    6. minStack.pop();
    7. minStack.top();      --> Returns 0.
    8. minStack.getMin();   --> Returns -2.

    题意

    设计一个栈结构，在实现栈的基础功能之外，还需要实现一个获取当前栈最小值的方法，每个操作的时间复杂度要求为$O(1)$。

    思路

    维护两个栈来实现输出最小值：一个为普通栈stack，一个用于保存与当前普通栈中元素相对应的最小值栈minStack。push新元素x时，如果当前minStack为空，或者x值小于等于minStack栈顶元素，说明x是加入后普通栈中的最小值，需要在minStack入栈；pop栈顶元素x时，如果x与minStack栈顶元素相同，说明x正是当前普通栈中的最小值，也需要在minStack出栈。

    代码实现

    1. class MinStack {
    2.     private LinkedList<Integer> stack;
    3.     private LinkedList<Integer> minStack;
    5.     /** initialize your data structure here. */
    6.     public MinStack() {
    7.         stack = new LinkedList<>();
    8.         minStack = new LinkedList<>();
    9.     }
    11.     public void push(int x) {
    12.         // 注意要使用<=，不然会引发NullPointerException
    13.         if (minStack.isEmpty() || x <= minStack.peek()) {
    14.             minStack.push(x);    
    15.         }
    16.         stack.push(x);
    17.     }
    19.     public void pop() {
    20.         int min = minStack.peek();
    21.         if (stack.peek() == min) {
    22.             minStack.pop();
    23.         }
    24.         stack.pop();
    25.     }
    27.     public int top() {
    28.         return stack.peek();
    29.     }
    31.     public int getMin() {
    32.         return minStack.peek();
    33.     }
    34. }
    36. /**
    37.  * Your MinStack object will be instantiated and called as such:
    38.  * MinStack obj = new MinStack();
    39.  * obj.push(x);
    40.  * obj.pop();
    41.  * int param_3 = obj.top();
    42.  * int param_4 = obj.getMin();
    43.  */