滑动窗口总结
滑动窗口简介
滑动窗口法其实就是双指针法，但是相较于一般的双指针法，其侧重点有所不同。一般的双指针法关注点在于遍历序列指针和用于存放结果的指针两者位置上的元素，而滑动窗口法关注的是两个指针之间的序列（我们将其称之为窗口）。
一般情况下，我们可以将定义好两个指针作为窗口的左右边界。这里暂时命名为low和high，其中low为左边界，high为右边界。通常境况下，high在遍历序列的过程中不断增加，以扩大窗口；当满足特定条件时，则通过调整low以缩小窗口；直到遍历过所有的元素。至于什么条件下开始缩小窗口，则视情况而定。
综上，我们使用滑动窗口的方法时，需要明确以下两点：如何表示窗口的状态、何种条件下增大或者缩小窗口。
滑动窗口伪代码
int mysolution(vector<int> nums){
int low=0,high=0,size=nums.size();
for(high=0;high<size;high++){ //通过遍历增加窗口右边界
计算当前窗口状态;
while(当窗口状态满足特定条件时){
调整窗口左边界;
更新窗口状态值;
}
}
return value;
}滑动窗口使用示例
209.长度最小的子数组
这里的子数组即为连续的子序列，要求为：序列和满足大于等于target值，但是需要记录其满足条件的序列中最小的长度。
窗口状态：窗口序列所有元素的和。
改变窗口的时机：遍历时扩大窗口，不断增大窗口，当窗口状态合法时缩小窗口。扩大和缩小窗口时需要实时更新窗口状态。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int low=0,high=0,size=nums.size(),sum=0; //low为窗口的左边界，high为右边界
int ans=INT_MAX; //ans用于记录最短的窗口长度，sum为窗口中元素的和（窗口状态）
for(high=0;high<size;high++){ //high为右边界，随着遍历进行增加
sum+=nums[high]; //向右扩展窗口时，更新窗口状态
while(sum>=target){ //如果窗口中的和满足条件，收缩窗口以获得最小的有效窗口长度
int templen=high+1-low;
ans=templen<ans?templen:ans; //则比较记录最小的满足条件的窗口大小
sum-=nums[low++]; //并从左边界缩小窗口，同时更新左边界low和窗口状态sum
}
}
return ans==INT_MAX?0:ans;
}
};904.水果成篮
此题可以等价于仅包含两种元素的最长子序列长度。序列中只能包含两种元素，且要记录所有满足的序列中最大的长度。
窗口状态：窗口中元素种类。
改变窗口的时机：遍历时扩大窗口，统计窗口中的元素，当窗口中出现第三个元素时，上一个窗口便是最长的合法窗口，此时记录窗口长度并缩小窗口直到出现新的合法窗口。扩大和缩小窗口时需要实时更新窗口状态。
//思路：题目等价于仅包含两种元素的最长子序列长度
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int,int> mp; //用于记录窗口状态
int ans=0;
int size=fruits.size();
int low=0,high=0,len;
for(high=0;high<size;high++){
mp[fruits[high]]--; //high指针遍历过程中统计每个元素出现的个数，用负数表示（不断扩大窗口长度）
while(mp.size()>=3){ //如果出现第三种元素则获取到一个最长合法的窗口，此时判定并更新窗口
len=high-low;
ans=len>ans?len:ans; //计算已获得的符合要求的窗口大小，并记录最大值
mp[fruits[low]]++; //然后调整窗口状态
if(mp[fruits[low]]==0) //从low开始依次解除元素个数的统计，即使用加法抵消high的统计
mp.erase(fruits[low]); //如果出现了个数为0的情况，则说明low+1~high中仅有两种元素了，即为新的窗口
low++; //更新左边界，直到获取到一个新的窗口
}
}
len=high-low; //结尾时也要计算，因为结尾时也一定是一个合法窗口
ans=len>ans?len:ans;
return ans;
}
};
Comments | NOTHING