239 滑动窗口最大值

题目

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

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

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：

输入：nums = [1], k = 1
输出：[1]

思路

维护一个单调递减的双向队列，在窗口尾将新元素与双向队列尾的元素大小对比，如果新元素大于队尾元素，将其弹出，并继续检查，直到队尾元素较大或者队列为空。这个双向队列头的元素即为窗口的最大元素。移动窗口，检查双向队头元素的序列是否为窗口外的序列，直到所有元素均为窗口内的序列。然后继续维护单调递减的双向队列。

代码

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

注意：每次进行队列弹出的时候需要检查队列是否为空，否则会报错。双向队列里面的元素为nums的序列，便于检查元素是否在滑动窗口内。

感谢 波波微课的LeetCode Hot 100
感谢 感谢 华南溜达虎 力扣 blind75 指导