A 29ms C solution


  • 0
    G
    struct MinListNode {
        int val;
        int minSoFar;
        struct MinListNode* next;
        struct MinListNode* last;
    };
    
    typedef struct {
        struct MinListNode* tail;
    } MinStack;
    
    void minStackCreate(MinStack *stack, int maxSize) {
        stack->tail = NULL;
    }
    
    void minStackPush(MinStack *stack, int element) {
        struct MinListNode* newNode = malloc(sizeof(struct MinListNode));
        newNode->val = element;
        newNode->next = NULL;
        newNode->last = stack->tail;
        if (!stack->tail) {
            newNode->minSoFar = element;
            stack->tail = newNode;
        }
        else {
            int min = stack->tail->minSoFar;
            stack->tail->next = newNode;
            stack->tail = newNode;
            newNode->minSoFar = min;
            if (element < min) {
                newNode->minSoFar = element;
            }
        }
    }
    
    void minStackPop(MinStack *stack) {
        struct MinListNode* freeMe = stack->tail;
        stack->tail = stack->tail->last;
    }
    
    int minStackTop(MinStack *stack) {
        return stack->tail->val;
    }
    
    int minStackGetMin(MinStack *stack) {
        return stack->tail->minSoFar;
    }
    
    void minStackDestroy(MinStack *stack) {
        while (stack->tail) {
            minStackPop(stack);
        }
    }
    

    I encountered the runtime error several times. For me, it was my attempt to malloc a stack in create(). It was confusing because I knew for a long time that it wouldn't do anything because of the depth of the pointer, but for some reason I never bothered to remove it. Consequently, I never assigned the tail of the real stack to NULL and my push function did not catch that the tail was nonexistent (it is initialized with garbage). It then attempted to dereference it in initializing min and crashes.


  • 0
    T

    // That push() method could be further optimized : )

    struct stack {
        int val;
        int min;
        struct stack* next;
    };
    
    typedef struct {
        struct stack* top;
    } MinStack;
    
    void minStackCreate(MinStack *stk, int maxSize) {
        stk->top = NULL;
    }
    
    void minStackPush(MinStack *stack, int element) {
        struct stack* neu = malloc(sizeof(struct stack));
        neu->val = element;
        neu->min = (stack->top && stack->top->min < element)? stack->top->min : element;
        neu->next = stack->top;
        stack->top = neu;
    }
    
    void minStackPop(MinStack *stack) {
        struct stack* temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
    }
    
    int minStackTop(MinStack *stack) {
        return stack->top->val;
    }
    
    int minStackGetMin(MinStack *stack) {
        return stack->top->min;
    }
    
    void minStackDestroy(MinStack *stack) {
        while (stack->top) minStackPop(stack);
    }

Log in to reply
 

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