洛谷p1886（滑动窗口，单调队列）_洛谷滑动窗口队列queue

这里简单来模拟一下：

1.开始front是0，rear是-1，两个while都不符合条件，执行rear++，此时，此时记下第一个元素的坐标0和值1

2.i++,变为1，第一个while不执行，因为第二个条件中的范围没有超出，再看第二个while，两个条件都符合，rear--，后++（此时rear变为0）。rear的下标变为1，值为3（想办法维护最大值在front的位置）
 3.i变为2，第一个while还是不执行，因为没有超出范围，第二个while也不执行，因为nums[i](此时是-1)小于maxQueue[rear].index(此时是3），然后rear++（变为1），rear的下标变为2，值变为-1，这时的i>=k-1（即已达到动画窗格的大小范围），输出front的值。此时的动画窗格中的元素排列是（3 -1），为什么1没有了呢，因为被我们弹出去了哈哈

4.以此类推...

#include <stdio.h>
#include <stdlib.h>
 
// Structure to represent a queue element
struct QueueElement {
    int index;
    int value;
};
 
// Function to print the minimum values in each sliding window
void printMinValues(const int nums[], int n, int k) {
    struct QueueElement* minQueue = (struct QueueElement*)malloc(n * sizeof(struct QueueElement));
    int front = 0, rear = -1;
 
    // Iterate through the array
    for (int i = 0; i < n; ++i) {
        // Remove elements that are out of the current window
        while (front <= rear && minQueue[front].index < i - k + 1) {
            front++;
        }
 
        // Remove elements that are smaller than the current element from the back of the queue
        while (front <= rear && nums[minQueue[rear].index] > nums[i]) {
            rear--;
        }
 
        // Add the current element to the queue
        rear++;
        minQueue[rear].index = i;
        minQueue[rear].value = nums[i];
 
        // Output the minimum value for each window
        if (i >= k - 1) {
            printf("%d ", minQueue[front].value);
        }
    }
    printf("\n");
 
    free(minQueue);  // Free the dynamically allocated memory
}
 
// Function to print the maximum values in each sliding window
void printMaxValues(const int nums[], int n, int k) {
    struct QueueElement* maxQueue = (struct QueueElement*)malloc(n * sizeof(struct QueueElement));
    int front = 0, rear = -1;
 
    
    for (int i = 0; i < n; ++i) {       
        while (front <= rear && maxQueue[front].index < i - k + 1) {
            front++;
        }
        //非空的队列，且front的坐标超过了k所包含的范围
   
        
        while (front <= rear && nums[maxQueue[rear].index] < nums[i]) {
            rear--;
        }
        
        //将当前元素的索引 i 入队，因为它可能成为后面窗口中的最大值。
        
        rear++;
        maxQueue[rear].index = i;
        maxQueue[rear].value = nums[i]; 
 
        // Output the maximum value for each window
        //窗口形成的条件就是
        if (i >= k - 1) {
            printf("%d ", maxQueue[front].value);
        }
    }
    printf("\n");
 
    free(maxQueue);  // Free the dynamically allocated memory
}
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
 
    int* nums = (int*)malloc(n * sizeof(int));
    //数组给的比较大,所以用动态内存分配
    for (int i = 0; i < n; ++i) {
        scanf("%d", &nums[i]);
    }
 
    printMinValues(nums, n, k);
    printMaxValues(nums, n, k);
 
    free(nums);  // Free the dynamically allocated memory
 
    return 0;
}