【剑指 offer】滑动窗口的最大值（双端队列）

1、题目描述

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。

例如，如果输入数组[2, 3, 4, 2, 6, 2, 5, 1]及滑动窗口的大小3,那么一共存在6个滑动窗口，它们的最大值分别为[4, 4, 6, 6, 6, 5]。

注意：

• 数据保证k大于0，且k小于等于数组长度。

样例：

输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3
输出: [4, 4, 6, 6, 6, 5]

2、问题描述：

3、问题关键：

• 可以建立双端队列，记录数组的下标，保证滑动窗口的队头保存的是当前窗口的最大值。
• 每次向后滑动一个，就判断当前的队头是否被滑出。
• 判断新的元素是否比之前加入的队列元素大，如果比以前大，那么就将以前比较小的弹出。

4、C++代码：

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> dq;
        for (int i = 0; i < nums.size(); i ++) {
            while(dq.size() && i - dq.front() >= k) dq.pop_front();//判断队头是否被滑出。
            while(dq.size() && nums[i] > nums[dq.back()]) dq.pop_back();//判断当前元素是否比队列的元素大。
            dq.push_back(i);
            if (i >= k - 1) res.push_back(nums[dq.front()]);
        }
        return res;
    }
};