MLE and accept after change all the vector to stack


  • 17
    I

    Below is my accepted code. If you change all the stack to vector, as well as all the top to back and push to push_back, pop to pop_back, then you'll get a MLE.

    WHY?
    Is there a tricky implement of stack in STL or does the vector brings me the fuss?
    thanks for your attention and answer!

    class MinStack {
    private:
        stack<int> sta;
        stack<int> minSta;
    public:
        void push(int x) {
            sta.push(x);
            if(!minSta.size() || minSta.top() >= x)
                minSta.push(x);
        }
    
        void pop() {
            if(!sta.empty()) {
                if(!minSta.empty() && sta.top() == minSta.top())
                    minSta.pop();
                sta.pop();
            }
        }
    
        int top() {
            if(!sta.empty()) return sta.top();
        }
    
        int getMin() {
            if(!minSta.empty()) return minSta.top();
        }
    };

  • 0
    S

    have the same question, anyone has an idea?


  • 4
    S

    The strategy that std::vector uses to allocate spaces is implementation dependent but it's something like http://en.wikipedia.org/wiki/Dynamic_array

    So a vector that has N element may takes upto 2*N spaces. That's why MLE happened.


  • 0
    I

    Thank you for your post. I got what you say, many thanks. Could you give me some idea about another question that how stack works? I have had the idea that stack is implemented by vector since I learned stack.


Log in to reply
 

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