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.

用priority queue维护最小值,当pop时注意检查栈顶是否和priority queue的顶部值相等,如果相等将queue顶部值Pop。


class MinStack {
public:
        vector<int> val;
        int ptr = -1;
        const int minVal = 0x7fffffff;
        priority_queue<int, vector<int>, greater<int>> pq;
    
        /** initialize your data structure here. */
        MinStack() {
        
        }
    
        void push(int x) {
                pq.push(x);
        
                ++ptr;
                if(ptr == val.size()) val.push_back(x);
                else val[ptr] = x;
        }
    
        void pop() {
                if(pq.top() == val[ptr]) pq.pop();
        
            --ptr;
        }
    
        int top() {
                return val[ptr];
        }
    
        int getMin() {
                if(!pq.empty())
                        return pq.top();
                else return minVal;
        }
};

Leave a Reply

Your email address will not be published. Required fields are marked *