Thoroughly explaining what's going on, a very concise solution accepted as best submission in C


  • 3

    Before we really get started, let's first make some points clear about this problem and also there are some complaints about the specification of the problem -> so misleading! Here is the detailed specification of the problem:

    • push will push the value to the stack - as a new top value;
    • pop will delete the top value of the stack - the only removing operation;
    • top will just return he top value of the stack - no removing;
    • getMin will just get the minimal value among the values in stack - no removing;

    The true question comes around now, how can we just get the minimal of the stack in constant time? First we need to think about this -> it's a stack -> values comes and goes at the rear of an array -> so we can just use another array <font color="#0000ff">mins</font> to store the so-far minimals which exactly means that when we are pushing values to the stack from the very beginning, we need to check whether the so-far minimal will be changed, if it's changed for the incoming new value, we need to push this value to the <font color="#0000ff">mins</font> array and so on and so on.

    the other array <font color="#0000ff">mins</font> will store the so-far minimals and should be updated in each push and pop operation to maintain this feature

    • so-far minimals means the minimals among values from the bottom till the top of the stack

    Bang! End of Story!

    Another typical example using space to reduce time cost:

    • space cost O(n)
    • time cost O(1)

    typedef struct
    {
        int *arr;
        int count;
        int *mins;
        int minCount;
    } MinStack;
    
    void minStackCreate(MinStack *stack, int maxSize)
    {
        stack->arr = (int*)malloc(sizeof(int)*maxSize);
        stack->mins = (int*)malloc(sizeof(int)*maxSize); //record the mins till the top of the arr;
        stack->count = 0;
        stack->minCount = 0;
    }
    
    void minStackPush(MinStack *stack, int element) //push it to arr normally, but meantime check whether we should push it to mins;
    {
        stack->arr[stack->count++] = element;
        if(stack->minCount==0 || element<=stack->mins[stack->minCount-1])
            stack->mins[stack->minCount++] = element;
    }
    
    void minStackPop(MinStack *stack) //pop will always pop the top -> the top of mins and arr;
    {
        int top = stack->arr[stack->count-1];
        if(stack->mins[stack->minCount-1] == top)
            stack->minCount--;
        stack->count--;
    }
    
    int minStackTop(MinStack *stack) //just return the top, needless to remove it;
    {
        return stack->arr[stack->count-1];
    }
    
    int minStackGetMin(MinStack *stack) //just return the min, needless to remove it;
    {
        return stack->mins[stack->minCount-1];
    }
    
    void minStackDestroy(MinStack *stack)
    {
        free(stack->arr);
        free(stack->mins);
    }

Log in to reply
 

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