Min Stack

Link: https://leetcode.com/problems/min-stack/

Constraint:

Idea

We could use two stacks, one responsible for regular stack operations; the other one responsible for keeping track of the minimux values so far, in decreasing order, which means the top element is the smallest and the bottom element is the largest.
For push calls, if the new inserted element is smaller than all the values we‘ve seen so far, we also add this number to the second stack.
For pop calls, if the removed element is equal to the top element in the second stack, we also pop this number from the second stack as well.

Code

class MinStack {
    Stack<Integer> st;
    Stack<Integer> minSoFar;
    /** initialize your data structure here. */
    public MinStack() {
        st = new Stack<>();
        minSoFar = new Stack<>();
    }
    
    public void push(int val) {
        st.push(val);
        if (minSoFar.isEmpty() || val <= minSoFar.peek()) {
            minSoFar.push(val);
        }
    }
    
    public void pop() {
        int top = st.pop();
        if (top == minSoFar.peek()) {
            minSoFar.pop();
        }
    }
    
    public int top() {
        return st.peek();
    }
    
    public int getMin() {
        return minSoFar.peek();
    }
}

• Time: ALl operations are O(1).
• Space: O(n) as we need to store all the elements we‘ve seen so far in the stack.

This solution here is using only one stack but its time and space complexity do not change.

Similar problem:

• Max Stack: https://leetcode.com/problems/max-stack/

Min Stack

原文：https://www.cnblogs.com/blackraven25/p/15113775.html