45ms C solution using stack


  • 0
    V
    struct stack {
        int* nums;
        int top;
    };
    
    struct stack* create(int depth);
    void destroy(struct stack* s);
    void push(struct stack* s, int v);
    int pop(struct stack* s);
    int empty(struct stack* s);
    
    int* nextGreaterElements(int* nums, int numsSize, int* returnSize)
    {
        int i, j;
    
        *returnSize = numsSize;
        int* res = malloc(sizeof(int) * numsSize);
    
        // Stack may contain twice all indices
        struct stack* s = create(numsSize * 2);
    
        // Init stack by pushing all indexes in reverse order
        for (i = numsSize - 1; i >= 0; i--)
            push(s, i);
    
        // Iterate array in reverse order
        for (i = numsSize - 1; i >= 0; i--) {
            
            // Pop index until greater number is found, or stack is empty
            for (j = pop(s); !empty(s) && nums[j] <= nums[i]; j = pop(s));
    
            if (nums[j] <= nums[i])
                res[i] = -1;
            else {
                res[i] = nums[j];
                push(s, j);
            }
    
            // Push current index as new greater number
            push(s, i);
        }
    
        destroy(s);
    
        return res;
    }
    
    struct stack* create(int depth)
    {
        struct stack* s = malloc(sizeof(struct stack));
        s->nums = malloc(sizeof(int) * depth);
        s->top = -1;
        return s;
    }
    
    void destroy(struct stack* s)
    {
        free(s->nums);
        free(s);
        return;
    }
    
    void push(struct stack* s, int v)
    {
        s->nums[++(s->top)] = v;
    }
    
    int pop(struct stack* s)
    {
        return s->nums[s->top--];
    }
    
    int empty(struct stack* s)
    {
        return s->top == -1;
    }
    

Log in to reply
 

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