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

1、思路

初见这个题可能会想到用两个指针来代表窗口的前后边界，但这样实现代码会非常复杂。最好的方式应该是用一个双端队列deque来构造单调栈，队列中存放的是元素下标，队头为窗口内最大元素的下标，当队头元素（下标）已经超出窗口范围时，我们把这个元素叫作过期元素，需要弹出。主要的四个步骤如下：

1. 队列不为空且队头元素已过期，则弹出队头元素；
2. 队列不为空且队尾元素 ≤ 当前元素，则弹出所有小于等于当前元素的队尾元素；
3. 插入当前元素；
4. 窗口已经完全进入数组中，将窗口中的最大值插入结果数组。

2、代码

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main()
{
    int n, windowSize;
    cin >> n >> windowSize;

    vector<int> nums, res;
    deque<int> q;

    for (int i = 0; i < n; ++ i)
    {
        int tmp;
        cin >> tmp;
        nums.push_back(tmp);
    }


    for (int i = 0; i < n; ++ i)
    {
        if (q.size() && q.front() <= i - windowSize) q.pop_front(); //1.
        while (q.size() && nums[q.back()] <= nums[i]) q.pop_back(); //2.
        q.push_back(i);                                             //3.
        if (i >= windowSize - 1) res.push_back(nums[q.front()]);    //4.
    }

    for (int i : res)
    {
        cout << i << " ";
    }

    return 0;
}