Code Interview Guide for Programmers CD15 Generating an Array of Windowed Maximums

题目链接：点击这里

首先要明确的是,The index is stored in the double-ended queue.同时,It is necessary to always ensure that the value of the array element corresponding to the index in the queue decreases gradually from the beginning to the end.

ri Used to traverse the array sequentially from left to right a[],同时 ri 也是滑动窗口的最右索引.

li 是滑动窗口的最左索引,即 li = ri - w + 1.

The steps to find the maximum value of the sliding window are as follows：

1. 如果 a[ri] >= a[队尾],则不断删除队尾,直到 a[队尾] > a[ri] 为止.

2. 将 ri 加入队尾.

3. 当 li < 0 的时候,意味着此时还没有出现一个完整的滑动窗口,直接跳过即可.

4. 当 li >= 0 的时候,如果队头过期,就移除队头,然后记录此时滑动窗口的最大值为 a[队头].

#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;

const int N = 1000010;

int a[N];

int main()
{
    
    int n, w;
    scanf("%d%d", &n, &w);
    
    for (int i = 0; i < n; i++)
    {
    
        scanf("%d", &a[i]);
    }
    
    deque<int> q;
    for (int ri = 0; ri < n; ri++)
    {
    
        // 如果a[ri] >= a[队尾],则不断删除队尾
        while (!q.empty() && a[ri] >= a[q.back()])
        {
    
            q.pop_back();
        }
        
        // 将ri加入队尾
        q.push_back(ri);
        
        int li = ri - w + 1;
        
        // 当li < 0的时候,意味着此时还没有出现一个完整的滑动窗口,直接跳过即可
        if (li < 0)
        {
    
            continue;
        }
        
        // 如果队头过期,就移除队头
        if (q.front() < li)
        {
    
            q.pop_front();
        }
        
        // 记录此时滑动窗口的最大值为a[队头]
        printf("%d ", a[q.front()]);
    }
    
    return 0;
}