传送门:LeetCode239.滑动窗口最大值

题意：有个长度为$k$的窗口在滑动，要求每次窗口内的最大的数。

法一:暴力

没什么好说的，对每次窗口内的数进行遍历找出最大值，时间复杂度$O(NK)$。显然会超时。

单调队列

这道题是单调队列的模版题，我们可以构建一个单调递减的队列来维护一个最大值:

• 把不在当前窗口内的数移出去
• 对${\mathtt{\text{nums}}}_i$,如果队列里面有比他小的数则通通移出去，因为比这个数小了那么后面一定不会取为最大值，因为一定存在${\mathtt{\text{nums}}}_i$比他大。

如nums = [1,3,-1,-3,5,3,6,7], k = 3:

队列为[1]时，此时3要进来，3比他大，故将他移出去,此时队列为[3]。

-1要进来，-1比他小故直接入队，此时形成了窗口，输出队头3,此时队列为[3,1]。

然后-3进来，与之前一样。

然后5进来，此时3已经不在窗口内了，故移出去，然后1,-3比5小故也排出，队列[5],输出5.

后面同理。

上述操作采用双端队列进行维护。

Code:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans;
        deque<int> q;
        for(int i = 0;i < n;i++) {
            while(!q.empty() && q.front() <= i - k)q.pop_front();
            while(!q.empty() && nums[q.back()] <= nums[i])q.pop_back();
            q.push_back(i);
            if(i >= k - 1)ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

时间复杂度为$O(NlogN)$,因为每个元素最多进出队列一次，每次时间复杂度为$O(logN)$,故总时间复杂度为$O(NlogN)$。

参考资料:OI-WIKI 单调队列