题解 | 239. 滑动窗口最大值

239. 滑动窗口最大值：****。

题意：

     给你一个数组nums，并给你值为k的滑动窗口，现在将窗口从数组左端到右端，每次移动一格，问每次移动的窗口内的最大值为多少。

     样例：数组nums={1,2,3,4,5}，k=3

     所以最大值数组为{3,4,5}。

做题思路：

     本文通过单调队列进行求解，并采用双端队列实现。为什么会是单调队列，当当前的节点比以往的节点大时，就将比该节点小的队列中的节点全都弹出，此时，节点会以从大到小排序，并且队首即为最大值。

 		for (int i=0;i<k;i++)
        {
            //维护队首最大值
            //当发现当前队尾小于当前节点时，排出该点
            while(!q.empty() && nums[i]>=nums[q.back()])
            {
                //删除队尾
                q.pop_back();
            }
            //此时的队列一定为从大到小排序
            q.push_back(i);
        }

     此时，只要加上窗口k的范围，就每次窗口内的最大值就是队首，那么怎么确定窗口范围呢，我们当前的队首记录的是该最大值节点的编号，所以，只要当遍历的节点超过该节点时，将队首排除即可，可能有人疑惑，排除队首最大值后，新窗口范围内的最大值能确认吗，当然可以，因为此时的队首就是该窗口的最大值，而这也是使用单调队列求解的原因。

 		for (int i=k;i<n;i++)
        {
            //同上，维护队首最大值 
            while(!q.empty() && nums[i]>=nums[q.back()])
            {
                q.pop_back();
            }
            q.push_back(i);
            //删除超越k范围的部分
            //上述代码确保了队列中一定为从大到小排序
            //但窗口会左边界会向右收缩，此时最大值有可能已经不在当前窗口的范围内
            //所以循环队首，当队首代表的编号<=左边界时，排出队首
            while(q.front()<=i-k)
            {
                //删除队首
                q.pop_front();
            } 
            //记录该窗口的最大值
            ans.push_back(nums[q.front()]);
        }

     可能细心的人有发现以上两段代码的范围是不一样的，那是因为维护左边界，要从i到k之后开始，否则在判断删除队首的时候就会卡循环，以下是AC代码。

		//双向队列
        //考虑本题找窗口最大值，所以队列应当严格遵守从大到小排序，当发现存在当前点大于队列中的点时，直接排除
        //使得记录的队首即是该窗口的最大值
        deque<int>q;
        int n=nums.size();
        //初始时，队列不用维护是否超出k，在找到第一个k范围内的最大值后，开始维护是否超出k值
        for (int i=0;i<k;i++)
        {
            //维护队首最大值
            //当发现当前队尾小于当前节点时，排出该点
            while(!q.empty() && nums[i]>=nums[q.back()])
            {
                //删除队尾
                q.pop_back();
            }
            //此时的队列一定为从大到小排序
            q.push_back(i);
        }
        //记录0~k中的最大值
        vector<int>ans={nums[q.front()]};
        for (int i=k;i<n;i++)
        {
            //同上，维护队首最大值 
            while(!q.empty() && nums[i]>=nums[q.back()])
            {
                q.pop_back();
            }
            q.push_back(i);
            //删除超越k范围的部分
            //上述代码确保了队列中一定为从大到小排序
            //但窗口会左边界会向右收缩，此时最大值有可能已经不在当前窗口的范围内
            //所以循环队首，当队首代表的编号<=左边界时，排出队首
            while(q.front()<=i-k)
            {
                //删除队首
                q.pop_front();
            } 
            //记录该窗口的最大值
            ans.push_back(nums[q.front()]);
        }
        return ans;