Share my 12ms C solution


  • 3
    J
    typedef struct {
    	int *base;
    	int *top;
    	int size;
    	int min;
    	int min_num;
    } MinStack;
    
    void minStackCreate(MinStack *stack, int maxSize) {
    	stack -> base = (int *)malloc(sizeof(int) * maxSize);
    	stack -> top = stack -> base;
    	stack -> size = 0;
    	stack -> min = INT_MAX;
    	stack -> min_num = 0;
    }
    
    void minStackPush(MinStack *stack, int element) {
    	*(stack -> top) = element;
    	stack -> top += 1;
    	if(element < stack -> min){
    		stack -> min = element;
    		stack -> min_num = 1;
    	}else if(element == stack -> min){
    		stack -> min_num += 1;
    	}
    	stack -> size += 1;
    }
    
    void minStackPop(MinStack *stack) {
    	stack -> top -= 1;
    	int cur = *(stack -> top);
    	stack -> size -= 1;
    	if(cur > stack -> min)
    		return;
    	else{
    		/* If we know more than one element that equals stack->min, 
    		 * we don't have to traverse the stack to find another stack->min 
    		 * while we already know its value! */
    		if(stack -> min_num > 1){
    			stack -> min_num -= 1;
    		}else{
    			int i = 0, min = INT_MAX, min_num = 0;
    			for(; i < stack -> size; i++){
    				if((stack -> base)[i] < min){
    					min = (stack -> base)[i];
    					min_num = 1;
    				}else if((stack -> base)[i] == min){
    					min_num += 1;
    				}
    			}
    			stack -> min = min;
    			stack -> min_num = min_num;
    		}
    	}
    }
    
    int minStackTop(MinStack *stack) {
    	stack -> top -= 1;
    	int res = *(stack -> top);
    	stack -> top += 1;
    	return res;
    }
    
    int minStackGetMin(MinStack *stack) {
    	return stack -> min;
    }
    
    void minStackDestroy(MinStack *stack) {
    	free(stack -> base);
    	stack -> base = NULL;
    	stack -> top = NULL;
    }

  • 0
    K

    well done, but if push and pop are way more frequently used, isn't this less efficient?


  • 0
    J

    less efficient than what? if you mean less efficient than two-stacks method mentioned in "solution",of course it is.. is this what you mean?


  • 0
    E
    typedef struct {
    int *min;
    int maxSize;
    //int *base;
    int *top;
    int num;
    } MinStack;
    
    void minStackCreate(MinStack *stack, int maxSize) {
        stack->min = (int *)malloc(maxSize*sizeof(int));
        stack->maxSize = maxSize;
        stack->top = (int *)malloc(maxSize*sizeof(int));
        stack->num = 0;
    }
    
    void minStackPush(MinStack *stack, int element) {
        if(stack->num>=stack->maxSize) return;
        *++stack->top = element;
        //stack->top++;
        if(stack->num==0){
            *++stack->min = element;
        }else{
            *++stack->min = *(stack->min-1)<element?*(stack->min-1):element;
        }
        stack->num++;
    }
    
    void minStackPop(MinStack *stack) {
        if(stack->num<=0) return;
        stack->top--;
        stack->min--;
        stack->num--;
    }
    
    int minStackTop(MinStack *stack) {
        if(stack->num<=0) return;
        return *stack->top;
    }
    
    int minStackGetMin(MinStack *stack) {
        if(stack->num<=0) return;
        return *stack->min;
    }
    
    void minStackDestroy(MinStack *stack) {
        free(stack->top-stack->num);
        free(stack->min-stack->num);
        stack->num = 0;
        stack->maxSize = 0;
    }
    

    also 12ms


  • 0
    Z

    there is a little error.
    *++stack->top = element;
    so the stack can accommodate only (maxSize -1) number.


Log in to reply
 

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