题目
给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
例如，如果输入数组[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]

解法：单调队列

模板题，写函数的时候可以用deque
时间复杂度O(n*k)，空间复杂度O(k)

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> q;
        for (int i = 0; i < nums.size(); i++) {
            while (q.size() && q.front() <= i - k) q.pop_front();    // 窗口大小
            while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();    // 单调性，确保队头最大
            q.push_back(i);
            if (i >= k - 1) ans.push_back(nums[q.front()]);    // 队头即为最大元素
        }
        return ans;
    }
};