Why MLE? I think i freed both stacks in the end


  • 1
    Q

    I use manually allocated stack rather than std::stack, but got memory limit exceeded.
    Edit: I corrected the mistake pointed out by @dragonmigo, and added the destructor, and even checked it with valgrind, no leaks were found, but still got MLE on the OJ.

    class MinStack {
    public:
        struct node {
            int val;
            node * next;
        };
        struct node * top_p;
        struct node * top_min;
    
        MinStack(){
            top_p = NULL;
            top_min = NULL;
        }
        void push(int x) {
            struct node * p = new node;
            p -> val = x;
            p -> next = top_p;
            top_p = p;
    
            if ( top_min == NULL || x <= top_min -> val) {
                struct node * min_p = new node;
                min_p -> val = x;
                min_p -> next = top_min;
                top_min = min_p;
            }
    
        }
    
        void pop() {
            if(top_p) {
                struct node * p = top_p ;
                if (p -> val == top_min -> val){
                        struct node * min_p = top_min ;
                        top_min = top_min -> next;
                        delete min_p;
                }
                top_p = top_p -> next;
                delete p;
            }
        }
    
        int top() {
            if(top_p) {
                return top_p -> val;
            }
            else {
                return 0;
            }
        }
        int getMin() {
            if(top_p) {
                return top_min -> val;
            }
            else {
                return 0;
            }
        }
        ~MinStack(){
            while(top_p!=NULL){
                struct node * p = top_p;
                top_p = top_p -> next;
                delete p;
            }
            while(top_min!=NULL){
                struct node * p = top_min;
                top_min = top_min -> next;
                delete p;
            }
    
        }
    };

  • 0
    D

    There are multiple places to be modified.

    1. top() and getMin() returns nothing for empty stack, which does not make sense. Return some error code instead.

    2. when you push() for the first time, this part of code does not deal with top_min very well:

               struct node * min_p = new node;
               min_p -> val = x;
               if (top_min != NULL){
                   min_p -> next = top_min;
               }
               top_min = min_p;
      

    Notice that the first created min_p is not initialized properly, which means min_p->next could be anything. This could cause problem when you pop last node, and min_p will be some unknown value.


  • 0
    Q

    I corrected the issue you pointed out, and added a destructor, and passed the valgrind test with a dataset(around 30), but still got MLE


  • 0
    C

    You didn't mention why this get MLE


Log in to reply
 

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