My C++ solution by my design data struct named big node stack


  • 0
    V
    const int capacity=100;
    bool cl=false;
    struct minstack 
    {
    	int * data;
    	minstack *next;
    	int size;
    	int lmin;
    	minstack(int *data):next(NULL),data(data),size(0){}
    };
    class MinStack {
    private:
    	minstack *head;
    	int min;
    public:
    	MinStack():head(NULL){}
        void push(int x) {
          if (head==NULL)
          {
    		  head=new minstack(new int[capacity]);
    		  min=x;
    		  head->lmin=x;
    		  head->data[head->size++]=x;
          }
    	  else
    	  {
    		  if (cl)
    		  {
    			  min=x;
    			  cl=false;
    		  }
    		  else
    		  {
    			  if(min>x)
    				min=x;
    		  }
    		  if (head->size<capacity)
    		  {
    			  if(head->lmin>x)
    				  head->lmin=x;
    			  head->data[head->size++]=x;
    		  }
    		  else
    		  {
    			  minstack *temp=new minstack(new int[capacity]);
    			  temp->next=head;
    			  head=temp;
    			  head->lmin=x;
    			  head->data[head->size++]=x;
    		  }
    	  }
    	}
        void pop() {
            if (head==NULL)
            {
    			return;
            }
    		if (head->size==0)
    		{
    			minstack *temp=head;
    			head=head->next;
    			free(temp);
    			if (head==NULL)
    			{
    				return;
    			}
    			if (head->data[--(head->size)]==min)//如果错size 分开写
    			{
    				minstack *temp=head->next;
    				if (head->size==0)
    				{
    					if(temp!=NULL)
    						min=temp->lmin;
    					else
    					{
    						cl=true;
    					}
    				}
    				else
    				{
    					min=head->data[head->size-1];
    					for (int i=head->size-2;i>=0;i--)
    					{
    						if (min>head->data[i])
    						{
    							min=head->data[i];
    						}
    					}
    				}
    				while(temp)
    				{
    					if (min>temp->lmin)
    					{
    						min=temp->lmin;
    					}
    					temp=temp->next;
    				}
    			}
    		}
    		else
    		{
    			if (head->data[--(head->size)]==min)//如果错size 分开写
    			{
    				minstack *temp=head->next;
    				if (head->size==0)
    				{
    					if(temp!=NULL)
    						min=temp->lmin;
    					else
    					{
    						cl=true;
    					}
    				}
    				else
    				{
    					min=head->data[head->size-1];
    					for (int i=head->size-2;i>=0;i--)
    					{
    						if (min>head->data[i])
    						{
    							min=head->data[i];
    						}
    					}
    				}
    				while(temp)
    				{
    					if (min>temp->lmin)
    					{
    						min=temp->lmin;
    					}
    					temp=temp->next;
    				}
    			}
    		}
    
        }
    
        int top() {
            return head->data[head->size-1];
        }
    
        int getMin() {
            return min;
        }
    };

Log in to reply
 

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