LeetCode #239 Sliding Window Max

Sliding_Window_Maximum.png

typedef struct {
    int capacity;
    int count;
    int *indices;
    int *inverse;
    int *keys;
    int(*cmp)(int, int);
}*IndexPriorityQueue;

void ipq_exch(int *indices, int *inverse, int i, int j) {
    int t = indices[I];
    indices[i] = indices[j];
    indices[j] = t;

    inverse[indices[i]] = I;
    inverse[indices[j]] = j;
}

int ipq_cmp(int *keys, int *indices, int i, int j, int(*cmp)(int, int)) { return cmp(keys[indices[i]], keys[indices[j]]); }

void ipq_swim(int *keys, int *indices, int *inverse, int k, int (*cmp)(int, int)) {
    int p = k / 2;
    while (k > 1 && cmp(keys[indices[k]], keys[indices[p]]) > 0) {
        ipq_exch(indices, inverse, k, p);
        k = p;
        p = k / 2;
    }
}

void ipq_sink(int *keys, int *indices, int *inverse, int n, int k, int(*cmp)(int, int)) {
    while (2 * k <= n) {
        int j = 2 * k;
        if (j < n && ipq_cmp(keys, indices, j, j + 1, cmp) < 0) j += 1;
        if (ipq_cmp(keys, indices, k, j, cmp) >= 0) break;
        ipq_exch(indices, inverse, k, j);
        k = j;
    }
}

void IndexPriorityQueueResize(IndexPriorityQueue ipq) {
    ipq->capacity = ipq->capacity == ipq->count ? 2 * ipq->capacity : ipq->capacity / 2;
    int *keys = malloc(sizeof(*keys) * (ipq->capacity + 1));
    int *indices = (int*)malloc((ipq->capacity + 1) * sizeof(int));
    int *inverse = (int*)malloc((ipq->capacity + 1) * sizeof(int));
    
    for (int i = 1; i <= ipq->count; i++) { 
        keys[i] = ipq->keys[I]; 
        indices[i] = ipq->indices[I];
        inverse[i] = ipq->inverse[I];
    }

    free(ipq->keys);
    free(ipq->indices);
    free(ipq->inverse);
    
    ipq->keys = keys;
    ipq->indices = indices;
    ipq->inverse = inverse;
}

void IndexPriorityQueueRelease(IndexPriorityQueue ipq) {
    if (ipq == NULL) return;
    free(ipq->keys);
    free(ipq->indices);
    free(ipq->inverse);
    free(ipq);
}

IndexPriorityQueue IndexPriorityQueueCreate(int(*cmp)(int, int), int capacity) {
    IndexPriorityQueue ipq = (IndexPriorityQueue)malloc(sizeof(*ipq));
    ipq->cmp = cmp;
    ipq->capacity = capacity;
    ipq->count = 0;
    ipq->keys = malloc((ipq->capacity + 1) * sizeof(int));
    ipq->indices = (int*)malloc((ipq->capacity + 1) * sizeof(int));
    ipq->inverse = (int*)malloc((ipq->capacity + 1) * sizeof(int));
    for (int i = 0; i <= ipq->capacity; i++) { ipq->inverse[i] = -1; }
    return ipq;
}

void IndexPriorityQueueInsert(IndexPriorityQueue ipq, int idx, int key) {
    ipq->count++;
    ipq->keys[idx] = key;
    ipq->indices[ipq->count] = idx;
    ipq->inverse[idx] = ipq->count;
    ipq_swim(ipq->keys, ipq->indices, ipq->inverse, ipq->count, ipq->cmp);
}

int IndexPriorityQueueHPKey(IndexPriorityQueue ipq) { return ipq != NULL ? ipq->keys[ipq->indices[1]] : INT_MIN; }

void IndexPriorityQueueDelete(IndexPriorityQueue ipq, int idx) {
    int index = ipq->inverse[idx];
    ipq_exch(ipq->indices, ipq->inverse, index, ipq->count--);
    ipq_swim(ipq->keys, ipq->indices, ipq->inverse, index, ipq->cmp);
    ipq_sink(ipq->keys, ipq->indices, ipq->inverse, ipq->count, index, ipq->cmp);
    ipq->keys[idx] = INT_MIN;
    ipq->inverse[idx] = -1;
}

int NumCmp(int a, int b) { 
    if (a == INT_MIN && b == INT_MIN) {
        return 0;
    } else if (a == INT_MIN) {
        return 1;
    } else if (b == INT_MIN) {
        return -1;
    } else {
        return a - b;
    }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    int *ret = (int*)malloc(numsSize * sizeof(*ret));
    *returnSize = 0;
    IndexPriorityQueue ipq = IndexPriorityQueueCreate(NumCmp, numsSize);

    for (int i = 0; i < k; i++) { IndexPriorityQueueInsert(ipq, i, nums[i]); }
    ret[(*returnSize)++] = IndexPriorityQueueHPKey(ipq);

    for (int i = k; i < numsSize; i++) {
        IndexPriorityQueueDelete(ipq, i - k);
        IndexPriorityQueueInsert(ipq, i, nums[I]);
        ret[(*returnSize)++] = IndexPriorityQueueHPKey(ipq);
    }
    return ret;
}