#滑动窗口
滑动窗口是利用双指针思想，两指针指向的元素之间形成窗口。
窗口类型可固定也可动态变化
##应用
一般用于数组或者字符串的数组处理
求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
这类问题一般用暴力会TLE
图示为窗口滑动
给你一个整数数组 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
-104 <= nums[i] <= 104
1 <= k <= nums.length
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int>sum;//答案数组 deque<int> q;//创建一个双端队列 for(int i=0;i<nums.size();i++) { while(q.size()&&q.front()<=i-k)//保证队列首端元素有效 q.pop_front(); while(!q.empty()&&nums[i]>=nums[q.back()])//保证队列内元素严格降序，有大的元素插入向前清除 q.pop_back(); q.push_back(i); if(i>=k-1) sum.push_back(nums[q.front()]);//每次向数组内插入当前窗口最大值 } return sum; } };
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
示例 1：
输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。
示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。
示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9
思路：
和上一题相似，不过需要开两个双端队列分别维护窗口内的最大值和最小值
这样我们只需要计算两个队列的队首的差值，即可知道当前窗口是否满足条件。
class Solution { public: int longestSubarray(vector<int>& nums, int limit) { deque<int> q;//最大值队列 deque<int> qq;//最小值队列 int j=0,sum=0; for(int i=0;i<nums.size();i++) { while(q.size()&&nums[i]>q.back())//维护最大队列 q.pop_back(); while(qq.size()&&nums[i]<qq.back())//维护最小队列 qq.pop_back(); q.push_back(nums[i]); qq.push_back(nums[i]); while(q.size()&&qq.size()&&(q.front()-qq.front()>limit))//清除无效的队列内元素 { if(nums[j]==q.front()) q.pop_front(); if(nums[j]==qq.front()) qq.pop_front(); j++; } sum=max(sum,i-j+1);//每次更新最大子数组长度 } return sum; } };
