程序员代码面试指南 CD15 生成窗口最大值数组

题目链接：点击这里

首先要明确的是，双端队列中存放的是索引。同时，要时刻保证队列中的索引对应的数组元素值从头到尾是逐渐减小的。

ri 用于从左往右依次遍历数组 a[]，同时 ri 也是滑动窗口的最右索引。

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

求滑动窗口最大值的步骤如下：

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;
}