C++ 2 stack based approach and priority queue approach


  • 0
    B
    /*
     * This should be constant time for push and pop, but it fails ...
     * stack is using a deque under the hood.
     */
    class MinStack2Stack {
    public:
        void push(int x) {
            mStack.push(x);
    
            if (mMinStack.empty() || x <= mMinStack.top()) {
                mMinStack.push(x);
            }
        }
    
        void pop() {
            assert(mStack.size() > 0);
    
            int top = mStack.top();
            mStack.pop();
    
            if (top == mMinStack.top()) {
                mMinStack.pop();
            }
        }
    
        int top() {
            assert(mStack.size() > 0);
            return mStack.top();
        }
    
        int getMin() {
            assert(mMinStack.size() > 0);
            return mMinStack.top();
        }
    
    private:
        std::stack<int> mStack; // here we could use std::list to really be constant time
        std::stack<int> mMinStack;  // syntax is std::stack<int, std::list<int> > mMinStack ...
    };
    
    /*
     * This should be log(n) for push and pop, since we're using a heap, but
     * succeed !
     */
    class MinStackOnePriorityQueue {
    public:
        void push(int x) {
            mStack.push(x);
            mPriorityQueue.push(x);
        }
    
        void pop() {
            int top = mStack.top();
            mStack.pop();
    
            if (top == mPriorityQueue.top()) {
                mPriorityQueue.pop();
            }
        }
    
        int top() {
            return mStack.top();
        }
    
        int getMin() {
            return mPriorityQueue.top();
        }
    
    private:
        std::stack<int> mStack;
        std::priority_queue<int, 
                            std::vector<int>, 
                            std::greater<int> > mPriorityQueue;
    };

  • 0
    B

    I'm quite puzzled ... I would have thought that my 2 stacks implementation would have been quite fast, while the priority queue one would have been slower.

    Maybe the one true constant time way is to use stack built on std::list instead ... let me try that ...


  • 0
    B

    OK the failure is not a "too slow" problem, it's just that my program is incorrect so it is crashing. I should fix it.


  • 0
    B

    I found my bug ...


  • 0
    D

    what do u mean by fail in stack implementation and success in priority que implementation


  • 0
    B

    I was getting a runtime error when submitting my MinStack2Stack based implementation, and I was confusing it with a time exceeded error. My code wasn't too slow, but incorrect. Once I fixed the bug the submission succeeded.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.