滑动窗口解决长度最小子数组和绝对值不超过限制的最长子数组

滑动窗口

滑动窗口思路就是维护一个窗口，不断滑动窗口、更新答案。
大致框架(具体情况要具体分析)如下：

int left = 0,right = 0;
while(right<s.size()){//增大窗口window.add(s[right]);right++;...while(缩小窗口的条件）{//缩小窗口window.remove(s[left]);left++;}
}

使用滑动窗口解决问题，需要考虑一下几点：

什么时候增大right扩大窗口？扩大窗口需要更新哪些数据？
什么时候需要增大left缩小窗口？缩小窗口需要更新哪些数据？
我们需要的结果应该在增大窗口还是缩小窗口时更新？

最小子数组

力扣209

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

测试样例

示例 1：输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：输入：target = 4, nums = [1,4,4]
输出：1
示例 3：输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

代码

int minSunArrayLen(int target, vector<int>& nums){int left = 0,right = 0;int num = target;int res = INT_MAX;while(right<nums,size()){num -= nums[right];while(num <= 0){res = min(res,right-left+1);num +=nums[left];//缩小窗口left++;}//增大窗口right++;}return res == INT_MAX ? 0 : res;
}

绝对值不超过限制的最长子数组

力扣1438

题目

给你一个整数数组 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

思路

要使得任意两个元素之间的绝对值差小于等于limit,只需要最大值和最小值的差小于或等于limit即可。所以问题的难点在于如何找到窗口中的最大和最小值。

思路1：可以使用自平衡的红黑数mulitset。
思路2：可以使用两个单调队列记录窗口中的最大和最小值。

代码

思路1：

int longestSubarray(vector<int>& nums, int limit) {int left = 0,right = 0;int res = INT_MIN;multiset<int>s;while(right<nums.szie()){s.insert(nums[right]);while(*s.rbegin() - *s.begin() > limit){			s.erase(s.find(nums[left]));left++;}res = max(res,right - left + 1);right++;}return res == INT_MIN ? 0 : res;
}

思路2：

int longestSubarray(vector<int>& nums, int limit) {int left = 0,right = 0;int res = INT_MIN;//单调递减队列维护最大值deque<int>downMax;//单调递增队列维护最小值deque<int>upMin;while(right<nums.size()){while(!downMax.empty()&&nums[right] > downMax.back()){downMax.pop_back();}while(!upMin.empty()&&nums[right] < upMin.back()){upMin.pop_back();}downMax.push_back(nums[right]);upMin.push_back(nums[right]);//缩小窗口while(!downMax.empty()&&!upMin.empty()&&downMax.front()-upMin.front() > limit){if(nums[left] == downMax.front()){downMax.pop_front();}if(nums[left] == upMin.front()){upMin.pop_front();}left++;}res = max(res,right-left+1);right++;}return res == INT_MIN ? 0 : res;
}