Share my c++ code 28ms


  • 0
    A
    class MinStack
    {
    size_t s_size;  //stack size
    size_t s_point;//stack index point
    
    size_t i_size;  //min stack size
    size_t i_point;//min stack index point
    
    
    public:
    int *stk;             //stack
    int *min_index; //min stack index
    
    int *buf;            //for realloc
    int min;             //min
    
    
    MinStack()
    {
        s_size =256;     //init size
        i_size =s_size;
        
        s_point = 0;
        i_point = 0;
        
        stk = (int*)malloc(sizeof(int)*s_size);
        min_index = (int*)malloc(sizeof(int)*i_size);
        
        min_index[0] = 0;    /* stk[0] is min. */
    
        min = INT_MAX;
    }
    ~MinStack()
    {
        free(stk);
        free(min_index);
    }
    
    void push(int x)
    {
    
        stk[s_point++] = x;
        if(x <= min)
        {
            min = x;
            min_index[i_point++] = s_point-1;
        }
        //if stack has 32768 elm than belows code no necessary in test case.
        if(s_point + 16 > s_size)
        {
            s_size += 256;
            
            buf = (int*)malloc(sizeof(int)*s_size);
            memcpy(buf,stk,sizeof(int)*(s_point));
            
            free(stk);
            stk = buf;
        }
        if(i_point + 8 > i_size)
        {
            i_size += 256;
            buf = (int*)malloc(sizeof(int)*i_size);
            memcpy(buf,min_index,sizeof(int)*(i_point));
            free(min_index);
            min_index = buf;
        }
    }
    
    void pop()
    {
        if(s_point != 0)
        {            
            if(stk[s_point-1] == min)
            {
                i_point--;
                min = stk[min_index[i_point-1]];
            }
            s_point--;
        }
    }
    int top() 
    {
        if(s_point == 0)
            return NULL;
        return stk[s_point-1];
    }
    int getMin()
    {
        return stk[min_index[i_point-1]]; 
    }
    };

  • 0

    Good answer! But I don't think you need a 'min_index[]'. You just need to maintain a single 'min' value. When popping item out, check if the 'min' is gonna be popped out. If yes, go through (O(n)) the stack and find a new 'min'. It's space complexity is constant. I also got a 28ms with this approach. You can even track the occurrence of the 'min' by another counter so as to further avoid unnecessary traverse.


  • 0
    A

    Thank you for answer.

    What I consider is
    insert(1), insert(2), insert(0), and pop() case.

    if no has min_index[] then lose minimum value after pop() operation.
    so needs new searching for find minimum value.

    but, has min_index[ ],
    then no needs new searching
    just access min_index [ i_point-1 ].

    Thank you !


Log in to reply
 

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