题目

题解

看题解有三个方法。最重要的是滑动窗口法，记录一下，其他的还有暴力法（超时）和动态规划法（没看懂，有时间再看）

1. 滑动窗口+单调递减队列

这个方法关键就是时刻可以快速取出滑动窗口中的最大值，使用剑指offer59-2中的单调递减队列即可实现，其他具体看注释

  • 时间复杂度$O(n)$
  • 空间复杂度$O(k)$，存k个数
class MaxDeque{//单调递减队列
    deque<int> max_d;
public:
    //若加入的新元素小于队列末尾的元素，则取出所有小的元素，再推入新元素
    void push(int value){
        while(!max_d.empty() && value > max_d.back()){
            max_d.pop_back();
        }
        max_d.push_back(value);
    }
    //若要弹出的元素等于当前队首的元素，即等于最大值，弹出当前值
    void pop(int value){
        if(!max_d.empty() && max_d.front() == value){
            max_d.pop_front();
        }

    }
    //队首就是最大值
    int get_max(){
        return max_d.front();
    }
};


class Solution {//一个方法。滑动窗口+单调队列法。
//这道题其实和剑指offer59-2有关联，需要用到那道题的知识点，即使用一个单调的双端队列    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MaxDeque max_d; 
        vector<int> res;
        for(int i = 0; i < nums.size(); ++i){
            //先把前k-1个数推入窗口
            if(i < k - 1){
                max_d.push(nums[i]);
            }
            //再添加一个新数，滑动窗口变完整
            //接着取出当前的最大值（用定义好的递减队列，时间复杂度O(1)
            //接着弹出滑动窗口的头部
            else{
                max_d.push(nums[i]);
                res.push_back(max_d.get_max());
                max_d.pop(nums[i-k+1]);
            }
        }
        return res;
    }
};