#define MAX_N 100000

typedef struct {
    int data[MAX_N];
    int front,rear;
} deque;

• MAX_N：定义了双端队列（deque）的最大容量。
• deque：定义了一个双端队列的结构体，其中data数组用于存储队列元素，front和rear分别表示队列的队首和队尾位置。

void initDeque(deque* dq) {
    dq->front = dq->rear = 0;
}

int isEmpty(deque* dq) {
    return dq->front == dq->rear;
}

void pushFront(deque* dq, int V) {
    dq->data[dq->rear++] = V;
}

void popFront(deque* dq) {
    dq->front++;
}

void popBack(deque* dq) {
    dq->rear--;
}

int getFront(deque* dq) {
    return dq->data[dq->front];
}

• initDeque：将双端队列的front和rear都初始化为 0，表示队列为空。
• isEmpty：判断双端队列是否为空，若front和rear相等，则队列为空。
• pushFront：将元素V添加到双端队列的队尾。
• popFront：移除双端队列的队首元素。
• popBack：移除双端队列的队尾元素。
• getFront：获取双端队列的队首元素。

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    int array[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &array[i]);
    }

    deque dq;
    initDeque(&dq);

    int res[n - k + 1];

    for (int i = 0; i < k; i++) {
        while (!isEmpty(&dq) && array[dq.data[dq.rear - 1]] <= array[i]) {
            popBack(&dq); 
        }
        pushFront(&dq, i);
    }
    res[0] = array[dq.data[dq.front]];

    for (int i = k; i < n; i++) {
        while (!isEmpty(&dq) && dq.data[dq.front] <= i - k) {
            popFront(&dq);
        }
        
        while (!isEmpty(&dq) && array[dq.data[dq.rear - 1]] <= array[i]) {
            popBack(&dq);
        }
        pushFront(&dq, i);

        res[i - k + 1] = array[dq.data[dq.front]];
    }

    for (int i = 0; i < n - k + 1; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", res[i]);
    }
    printf("\n");

    return 0;
}

• 读取输入：首先读取数组的长度n和滑动窗口的大小k，然后读取数组的每个元素。
• 初始化双端队列：创建一个双端队列dq并初始化。
• 处理第一个滑动窗口：遍历数组的前k个元素，将元素的下标添加到双端队列中，同时保证队列中的元素对应的数组值是单调递减的。将第一个滑动窗口的最大值存入结果数组res中。
• 处理后续滑动窗口：对于每个后续的滑动窗口，先移除不在当前窗口内的元素，再将新元素添加到队列中，保证队列的单调性。将当前窗口的最大值存入结果数组res中。
• 输出结果：遍历结果数组res，输出每个滑动窗口的最大值。

体会：

学习这个关于滑动窗口最大值的题目，能带来多方面深刻体会。在算法思维上，明白了如何通过巧妙的数据结构（双端队列）和逻辑设计（维护单调队列），将看似复杂的滑动窗口问题简化，高效解决。这有助于培养化繁为简、创新解题的思维模式。从数据结构运用角度，加深了对双端队列特性的理解，认识到它在灵活处理数据进出场景中的优势。