Leetcode 239. 滑动窗口最大值

题目

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

思路

参考题解：https://leetcode.cn/problems/sliding-window-maximum/solution/tu-jie-suan-fa-dan-diao-dui-lie-zui-jian-h012/

代码

class Solution {
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    
        deque<int> q;// 双端队列
        vector<int>res;

        for(int i = 0; i < nums.size(); i++)
        {
    
            while(q.size() && i - k + 1 > q.front())
            {
    
                q.pop_front();// 判断对头是否在滑动窗口范围之内
            }
            while(q.size() && nums[i] >= nums[q.back()])
            {
    
                // 当前元素大于队尾元素
                q.pop_back();// 维护单调递减队列
            }
            q.push_back(i);// 将当前元素插入队尾

            if(i >= k - 1)
            {
    
                res.push_back(nums[q.front()]);// 滑动窗口的元素达到了k个 将队头元素插入结果数组中
            }
        }

        return res;
    }
};