Memory exceeds by using a single vector


  • 1
    C
    class MinStack {
    public:
        void push(int x) {
            v.push_back(x);
            if(min>x)
            min=x;
        }
    
        void pop() {
            int x=v[v.size()-1];
            v.pop_back();
            if(x<=min)
            {
                vector<int>::iterator it=min_element(v.begin(),v.end());
                min=*it;
            }
        }
    
        int top() {
           return v[v.size()-1];
        }
    
        int getMin() {
    		
            return min;
        }
        
        vector<int> v;
        int min;
    };

  • 0
    C

    Why is this code exceeding memory limit? min_element is a library function


  • 0
    C
    struct Nod
    { 
        int val;
        Node *next, *prev;
        Node(int i) { val=i;next=NULL; prev=NULL;  }
    };
        
    class MinStack
    {
    public:
        void push(int x)
        {
            Node *n=new Node(x);
            if(head==NULL) { head=n; tail=n;}
            else
            {
                n->prev=tail;
                tail->next=n;
                tail=n;
            }
            sz++;
            if(min>x)  min=x;
        }
    
        void pop()
        {
            int x;
            if(sz>0)
            {
                x=tail->val;
                Node *tmp=tail->prev;
                if(tmp) tmp->next=NULL;
                delete tail;
                tail=tmp;
                sz--;
    
                if(x<=min && sz>0)
                {
                    //update min
                    Node *hd=head;
                    while(hd)
                    {
                        if(hd->val<min) min=hd->val;
                        hd=hd->next;
                    }
                }
                if(sz==0) head=NULL;
           }
        }
    
        int top() 
        {
            if(sz>0) return tail->val;
            else return INT_MAX;
        }
    
        int getMin() { return min; }
        
    	MinStack() { head=NULL; tail=NULL; min=INT_MIN; sz=0; }
            
        Node *head, *tail;
        int min,sz;
        
    };
    enter code here
    

  • 0
    C

    Even this simple, straight code above got memory limit exceeded. Help?


  • 0
    E

    Does pop operation return result in constant time? Maybe iterator is the problem.


Log in to reply
 

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