239. 滑动窗口最大值

1.题目描述

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例:

2.思路（双向队列）

使用双向队列max_index存储下标。max_index有以下特点:

1.变量的最前端（也就是 max_index.front()）是此次遍历的最大值的下标

2.当我们遇到新的数时，将新的数和双项队列的末尾（也就是max_index.back()）比较，如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才停止，做法有点像使用栈进行括号匹配。

3.双项队列中的所有值都要在窗口范围内

特点一只是方便我们获取每次窗口滑动一格之后的最大值，我们可以直接通过 max_index.front() 获得

通过特点二，可以保证队列里的元素是从头到尾降序的，由于队列里只有窗口内的数，所以他们其实就是窗口内第一大，第二大，第三大… 的数。

特点三，因为只要窗口内第一大元素也就是这个 max_index.front() 在窗口内，那我们可以不用管第二大第三大元素在不在区间内了。因为答案一定是这个第一大元素。如果 max_index.front() 不在窗口内，则将其弹出，第二个大元素变成第一大元素，第三大元素变成第二大元素以此类推。

3.代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        if(nums.empty()){
            return res;
        }
        deque<int> max_index;
        for(int i = 0;i < nums.size();++i){
            while(!max_index.empty() && nums[i] >= nums[max_index.back()]){//保证双向队列是递减的
                max_index.pop_back();
            }
            max_index.push_back(i);
            if(max_index.front() == (i-k)){
                max_index.pop_front();
            }
            if(i >= k-1){
                res.push_back(nums[max_index.front()]);
            }
        }
        return res;
    }
};
           

4.复杂度分析

时间复杂度：O(n)，每个元素被处理两次- 其索引被添加到双向队列中和被双向队列删除。

空间复杂度：O(n)，输出数组使用了O(N−k+1) 空间，双向队列使用了O(k)。