生成窗口最大值数组

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int val;
    struct node *prev;
    struct node *next;
} Node;

Node *createNode(int val);
void addLast(int val);
void removeFirst();

// the head and tail of the double-ended queue
Node *pHead = NULL;
Node *pTail = NULL;

int main(void) {
    int n, w;
    scanf("%d%d", &n, &w);
    int *arr = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }

    int l = 0, r = 0;
    while (r < w) {
        addLast(arr[r++]);
    }

    int index = 0;
    int *res = (int *) malloc((n - w + 1) * sizeof(int));
    for (;;) {
        res[index++] = pHead->val;
        if (arr[l++] == pHead->val)
            removeFirst();
        if (r == n)
            break;
        addLast(arr[r++]);
    }
    // print result
    for (int i = 0; i < index; i++) {
        printf("%d ", res[i]);
    }
    // release memory
    while (pHead != NULL)
        removeFirst();
    free(arr);
    free(res);
    return 0;
}

Node *createNode(int val) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

void addLast(int val) {
    Node *pNode = NULL;
    while (pHead != NULL && val > pTail->val) {
        pNode = pTail;
        if (pHead == pTail) {
            pHead = NULL;
            pTail = NULL;
        } else {
            pTail = pTail->prev;
            pTail->next = NULL;
        }
        free(pNode);
    }
    pNode = createNode(val);
    if (NULL == pHead) {
        pHead = pNode;
        pTail = pNode;
        return;
    }
    pTail->next = pNode;
    pNode->prev = pTail;
    pTail = pNode;
}

void removeFirst() {
    Node *pNode = pHead;
    if (pHead == pTail) {
        pHead = NULL;
        pTail = NULL;
    } else {
        pHead->next->prev = NULL;
        pHead = pHead->next;
    }
    free(pNode);
}