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 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2输入nums [1], k 1输出[1]思路维护一个单调递减的双向队列在窗口尾将新元素与双向队列尾的元素大小对比如果新元素大于队尾元素将其弹出并继续检查直到队尾元素较大或者队列为空。这个双向队列头的元素即为窗口的最大元素。移动窗口检查双向队头元素的序列是否为窗口外的序列直到所有元素均为窗口内的序列。然后继续维护单调递减的双向队列。代码class Solution{public: vectorintmaxSlidingWindow(vectorintnums, int k){dequeintdq;vectorintres;for(int i0;ik;i){while(!dq.empty()nums[i]nums[dq.back()]){dq.pop_back();}dq.push_back(i);}res.push_back(nums[dq.front()]);for(int rk;rnums.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 指导