Please help me figure out why my solution is Memory Limit Exceed


  • 0
    D

    Please help me figure out why my solution is Memory Limit Exceed
    I just use the standard binary min heap strategy

    #include "stdafx.h"
    #include<vector>
    #include<iostream>
    using namespace std;
    class MinStack {
    public:
        vector<int> heap;
        int sz;
        MinStack():sz(0){}
    	bool empty()
    	{
    		return sz==0;
    	}
        void push(int x) {
    		if(sz<heap.size())
    		{
    			heap[sz++]=x;
    		}
    		else
    		{
    			heap.push_back(x);
    			sz++;
    		}
            buttonUpAdjust();
        }
    
        void pop() {
            heap[0]=heap[sz-1];
            sz--;
            topDownAdjust();
        }
    
        int top() {
            return heap[0];
        }
    
        int getMin() {
            return heap[0];
        }
        void topDownAdjust()
        {
            int curPos=0;
            while(curPos<sz)
            {
                int left=leftChild(curPos);
                int right=rightChild(curPos);
                int minPos=left;
                if((left<sz)||(right<sz))
                {
                    if((right<sz)&&(heap[right]<heap[left]))
                    {
                        minPos=right;
                    }
                    if(heap[minPos]<heap[curPos])
                    {
                        int tmp=heap[minPos];
                        heap[minPos]=heap[curPos];
                        heap[curPos]=tmp;
                        curPos=minPos;
                    }
                    else
                    {
                        break;
                    }
                }
                else
                {
                    curPos=left;   
                }
            }
        }
        void buttonUpAdjust()
        {
            int pos=sz-1;
            while((pos!=0)&&(heap[father(pos)]>heap[pos]))
            {
                int tmp=heap[father(pos)];
                heap[father(pos)]=heap[pos];
                heap[pos]=tmp;
                pos=father(pos);
            }
        }
        int father(int pos)
        {
            return (pos-1)/2;
        }
        int leftChild(int pos)
        {
            return 2*pos+1;
        }
        int rightChild(int pos)
        {
            return 2*pos+2;
        }
    };

  • 0
    D

    I have figured out the mistake. I misunderstood the problem, the problem need MinStack to firstly behave like a stack, but I ignored this limitation.


Log in to reply
 

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