题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

解析

此题使用单调队列解决，分享一段有趣的评论：

单调队列真是一种让人感到五味杂陈的数据结构，它的维护过程更是如此.....就拿此题来说，队头最大，往队尾方向单调......有机会站在队头的老大永远心狠手辣，当它从队尾杀进去的时候，如果它发现这里面没一个够自己打的，它会毫无人性地屠城，把原先队里的人头全部丢出去，转身建立起自己的政权，野心勃勃地准备开创一个新的王朝.....这时候，它的人格竟发生了一百八十度大反转，它变成了一位胸怀宽广的慈父！它热情地请那些新来的“小个子”们入住自己的王国......然而，这些小个子似乎天性都是一样的——嫉妒心强，倘若见到比自己还小的居然更早入住王国，它们会心狠手辣地找一个夜晚把它们通通干掉，好让自己享受更大的“蛋糕”；当然，遇到比自己强大的，它们也没辙，乖乖夹起尾巴做人。像这样的暗杀事件每天都在上演，虽然王国里日益笼罩上白色恐怖，但是好在没有后来者强大到足以干翻国王，江山还算能稳住。直到有一天，闯进来了一位真正厉害的角色，就像当年打江山的国王一样，手段狠辣，野心膨胀，于是又是大屠城......历史总是轮回的。

解答

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //构建存储最大值的数组
        vector<int> res;

        if(nums.size() == 0 || k == 0)
        {
            return res;
        }
        //单调递减序列
        deque<int> dq;
        //一开始滑动窗口不包含K个元素，不是合格的滑动窗口
        for(int i = 0; i < k; i++)
        {
            while(!dq.empty() && dq.back() < nums[i])
            {
                dq.pop_back();
            }
            dq.push_back(nums[i]);
        }

        res.push_back(dq.front());

        for(int i = k; i < nums.size(); i++)
        {
            if(dq.front() == nums[i-k])
            {
                dq.pop_front();
            }

            while(!dq.empty() && dq.back() < nums[i])
            {
                dq.pop_back();
            }
            dq.push_back(nums[i]);

            res.push_back(dq.front());
        }

        return res;
    }
};