算法必刷系列之滑动窗口

本文主要是介绍算法必刷系列之滑动窗口，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

滑动窗口

滑动窗口的问题一般分为两类，一类是窗口大小固定，求解窗口内数据的最值问题，一类是窗口大小可变，求解窗口长度的最值问题。核心思想是使用快慢型双指针模拟滑动窗口，利用指针的移动模拟窗口的滑动，对窗口中不断变换的数据进行比较。需要注意的是边界处理。

子数组最大平均数

leetcode643

固定窗口大小，求窗口内数据和的最大值。初始时，计算下标从0开始窗口大小为k的和，作为和的最大值，将固定窗口每次向右移动1个单位，即最左侧的元素滑出，右侧的下一个元素滑入，计算和，进行比较

public double findMaxAverage(int[] nums, int k) {int maxSum = 0;for(int i=0;i<k;i++){maxSum+=nums[i];}int sum = maxSum;int right = k;while(right<nums.length){sum=sum+nums[right]-nums[right-k];maxSum = Math.max(sum,maxSum);right++;}return (double)maxSum/k;
}

最长连续递增子序列

leetcode674
窗口大小可变，如果序列递增，继续添加元素到序列中，计算当前最长递增序列，进行比较，否则窗口滑动到当前位置，继续寻找递增序列

public int findLengthOfLCIS(int[] nums) {int left = 0;int right = 1;int maxLen = 1;while(right<nums.length){if(nums[right]-nums[right-1]<=0){left = right;}maxLen = Math.max(maxLen,right-left+1);right++;}return maxLen;
}

无重复的最长子串

leetcode3
使用map存储当前遍历到的字符，key表示字符本身，value表示字符下标，当子串不重复时，存储，继续遍历，计算最大长度，重复时，将窗口滑动到重复元素的下一位置，继续操作

public int lengthOfLongestSubstring(String s) {if(s.length()==0){return 0;}Map<Character,Integer> map = new HashMap<Character,Integer>();char[]chars = s.toCharArray();int left = 0;int right = 1;int maxLen = 1;map.put(chars[left],left);while(right<chars.length){if(map.containsKey(chars[right])){left = Math.max(map.get(chars[right])+1,left);}map.put(chars[right],right);maxLen = Math.max(right-left+1,maxLen);right++;}return maxLen;
}

长度最小的子数组

leetcode209
窗口右侧不断右移，直至数据和超过target，计算长度并比较，窗口左侧右移，直至数据和小于target,计算长度并比较

public int minSubArrayLen(int target, int[] nums) {int left = 0;int right = 0;int sum = 0;int minLen = Integer.MAX_VALUE;while(right<nums.length){sum+=nums[right++];while(sum>=target){minLen = Math.min(right-left,minLen);sum-=nums[left++];} }return minLen==Integer.MAX_VALUE?0:minLen;
}

盛水最多的容器

leetcode11
初始时，窗口占满整个数组，计算水容量，之后不断缩小短板，计算水容量

public int maxArea(int[] height) {int left = 0;int right = height.length-1;int maxNum = 0;while(left<right){if(height[left]<height[right]){maxNum = Math.max((right-left)*height[left],maxNum);left++;}else{maxNum = Math.max((right-left)*height[right],maxNum);right--;}}return maxNum;
}

字符串的排列

leetcode567
以短串长度为窗口大小，在长串中滑动，比较两串字符个数是否相同，可通过数组对应位置的值作为元素出现次数来进行比较

public boolean checkInclusion(String s1, String s2) {if(s1.length()>s2.length()){return false;}int n = s1.length();int[] count1 = new int[26];int[] count2 = new int[26];char[] chars1 = s1.toCharArray();char[] chars2 = s2.toCharArray();for(int i=0;i<n;i++){count1[chars1[i]-'a']++;count2[chars2[i]-'a']++;}if(Arrays.equals(count1,count2)){return true;}int right = n;while(right<s2.length()){count2[chars2[right]-'a']++;int left = right-n;count2[chars2[left]-'a']--;if(Arrays.equals(count1,count2)){return true;}right++;}return false;
}

字符串中所有的字母异位

leetcode438
与上一题类似，找到字母异位后记录开始下标

public List<Integer> findAnagrams(String s, String p) {List<Integer> res = new ArrayList<>();if(p.length()>s.length()){return res;}int n = p.length();int[] count1 = new int[26];int[] count2 = new int[26];char[] chars1 = p.toCharArray();char[] chars2 = s.toCharArray();int left = 0;for(int i=0;i<n;i++){count1[chars1[i]-'a']++;count2[chars2[i]-'a']++;}if(Arrays.equals(count1,count2)){res.add(left);}int right = n;while(right<s.length()){count2[chars2[right]-'a']++;left = right-n;count2[chars2[left]-'a']--;if(Arrays.equals(count1,count2)){res.add(left+1);}right++;}return res;
}

滑动窗口最大值

leetcode239
将遍历到的元素以二元组的形式存放在大顶堆中，二元组分别元素和对应下标，最值即为堆顶元素，判断最值之前，需要将不属于滑动窗口范围内的堆顶元素移除

public int[] maxSlidingWindow(int[] nums, int k) {int[] ans = new int[nums.length - k + 1];PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b)->(b[0]-a[0]));int res = 0;int left = 0;int right = k;for (int i = left; i < right; i++) {maxHeap.offer(new int[]{nums[i],i});}ans[res++] = maxHeap.peek()[0];while (right < nums.length) {maxHeap.offer(new int[]{nums[right],right++});left++;while(maxHeap.peek()[1]<left){maxHeap.poll();}ans[res++] = maxHeap.peek()[0];}return ans;
}