LeetCode 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]

提示：

1 <= nums.length <= 105^55
-104^44<= nums[i] <= 104^44
1 <= k <= nums.length

单调队列+滑动窗口，队列从头到尾依次递减，一边滑动一边更新队列，队首就是答案：

classSolution{public:vector<int>maxSlidingWindow(vector<int>&nums,intk){vector<int>ans(nums.size()-k+1);deque<int>q;for(inti=0;i<nums.size();++i){// 保证队列是单调递减的，如果末尾元素与当前元素相同，则弹出末尾元素，队列中不会有重复元素while(!q.empty()&&nums[i]>=nums[q.back()]){q.pop_back();}q.push_back(i);if(i<k-1){continue;}// 保证队列头在窗口内if(q.front()<i-k+1){q.pop_front();}ans[i-k+1]=nums[q.front()];}returnans;}};

如果nums的大小为n，其中的元素种类为m，则此算法时间复杂度为O(n)，空间复杂度为O(min(m,k))。