Sunday, June 7, 2015

[LeetCode] 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.
Note: when the element to push is equal to the top of min stack, it should be push.
class MinStack {
    stack<int> elements;
    stack<int> minElements;
public:
    void push(int x) {
        elements.push(x);
        if(minElements.empty() || 
                x <= minElements.top()) {
            minElements.push(x);
        }
    }

    void pop() {
        if(elements.empty()) return;
        
        int t = elements.top();
        if(t == minElements.top()){
            minElements.pop();
        }
        elements.pop();
    }

    int top() {
        return elements.top();
    }

    int getMin() {
        return minElements.top();
    }
};