经典单调队列问题

题目描述

Problem: 239：滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字，且滑动窗口每次只向右移动一位。
返回每个滑动窗口看到的最大值的序列。

思路

这种题看上去就要用单调队列来减少时间复杂度。

朴素的想法是一次遍历，每次拿出最大值的过程应该是O(k)的时间复杂度。但实际上每次滑动框移动一次，（最多）只会导致一个老元素过时和一个新元素出现，所以在每次遍历拿出最大值的过程中，会重复扫描很多元素。于是我们可以维护一个单调递减的队列q，将每次取最大值的时间复杂度降为$O(1)$。

每次滑动框移动一次，都会导致一个老元素过时和一个新元素出现，我们只需要在这个过程中维护单调递减队列。

解题过程

1. 在遍历的过程中，首先判断队首元素$q[0]$是否已经过时，如果过时就让其出列;
2. 再考虑新元素加入队列的过程，由于新元素一定要在队列中，于是从尾部开始pop队列的元素，直到新元素可以顺利加入并形成单调队列;
3. 将队首元素$q[0]$加入$result$中。

复杂度

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

code

代码实现时，这种双端都要进出的结构应该用deque（双端队列）实现。这里有deque的基本用法介绍。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& heights, int limit) {
        vector<int> res;
        deque<int> q;

        if(heights.empty()) return res; //空队列情况

        for(int i = 0; i <= heights.size() - 1; i++)
        {
            if(i - limit >= 0 && q[0] == heights[i - limit]) //要被剔除
            {
                q.pop_front();
            }
            while(!q.empty() && q.back() < heights[i]) //将列表中所有小于加入元素的数删掉，以保证队列的递减性
            {
                q.pop_back();
            }
            q.push_back(heights[i]); //加入新元素

            if(i >= limit - 1) res.push_back(q[0]); //在窗口完整后，向res中加答案
        }

        return res;
    }
};