LeetCode.239 滑动窗口最大值

单调队列介绍

我们已经知道，单调栈的栈底是封闭的，元素可以从栈顶进出来保持栈内元素的单调性。
单调队列在此基础上，打开了栈底作为队首，原来的栈顶作为队尾。但是和普通的双端队列不同的是，队头的一端只能出不能进，而双端队列的两端元素进出自由。
假设现在维护一个从队头到队尾元素递增的单调队列，这部分的代码和单调栈没有任何区别。

for (int i = 0; i < n; i++)
{
    while (!mono_queue.empty() && nums[i] > nums[mono_queue.back()])
            mono_queue.pop_back();
    mono_queue.push_back(i);
}

然而队列毕竟是队列，在满足特定条件时，队头的元素需要出队。

if(condition == true) mono_queue.pop_front();

LeetCode.239 滑动窗口最大值

原题链接
由于单调队列本身的性质，队首元素肯定是队列中元素的最大值或者最小值（取决于队列元素是单调增还是单调减）。本题题意肯定是要维护一个单调递减队列，使得队首元素是最大值。
然而滑动窗口本身有大小限制。当窗口向右滑动，当前队首元素已经不存在于当前窗口所界定的下标范围内时，队首元素就需要从队首出队，获取新的队首元素，即新的窗口中的最大值。
注意：因为窗口一次移动一格，所以如果队首元素因为已经不在范围内而从队首出队后，新的队首元素必然在新窗口内。
AC代码：

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        deque<int> mono_queue;
        vector<int> ans;
        int n = nums.size();
        for (int i = 0; i < k; i++)    //先处理第一个窗口
        {
            while (!mono_queue.empty() && nums[i] > nums[mono_queue.back()])
                mono_queue.pop_back();

            mono_queue.push_back(i);
        }

        ans.push_back(nums[mono_queue.front()]);

        for(int i = k; i < n; i++)    //窗口开始移动
        {
            while (!mono_queue.empty() && nums[i] > nums[mono_queue.back()]) //维护单调性
                mono_queue.pop_back();

            mono_queue.push_back(i);    //每移动一格，会有新元素入队
            if(mono_queue.front() < i - k + 1) mono_queue.pop_front();//队首还在窗口范围内么
            ans.push_back(nums[mono_queue.front()]);
        }

        return ans;
    }
};