菜鸟追梦旅行

这个屌丝很懒，什么也没留下！

热门标签

【LeetCode】滑动窗口系列总结_leetcode 滑动窗口

作者：菜鸟追梦旅行 | 2024-04-26 10:49:08

踩

leetcode 滑动窗口

滑动窗口系列总结

用到滑动窗口的题目类型
滑动窗口模版
固定窗口
单调队列解决滑动窗口问题
- 239. 滑动窗口最大值

参考：
LeetCode刷题顺序
滑动窗口类型(Sliding window)
labuladong的滑动窗口模版

用到滑动窗口的题目类型

关于求最长/最小子串之类的
或者特定长度的要求

滑动窗口模版

滑动窗口的思想：维护一个left、right 然后right右移扩张窗口，直到right到最右边停止。left右移就是收缩窗口，收缩窗口的条件为此时窗口满足题目要求了。

窗口右移时要做的事:
- 判断是否为答案需要的，是need需要的就更新进窗口
- 要注意更新目前进度，用来判断窗口内数据是否已满足条件
当窗口内的数据满足条件窗口左移，如何判断窗口内的数据满足条件
- 这个条件就是扩张窗口和收缩窗口时要更新的
  比如找最小字符串时用valid来记录窗口内满足条件的字符个数，扩张窗口的时候valid++，收缩窗口时valid–
窗口满足条件后，进行窗口左移
- 左移过程中，如果左移后就不满足条件了说明找到一个解了

java模板：


void slidingWindow(String s,String t){
        HashMap<Character,Integer> need = new HashMap<Character, Integer>();//need 是需要凑齐的字符
        HashMap<Character,Integer> window = new HashMap<Character, Integer>(); // window是窗口中的字符
        // 把t中 每个字符出现的次数记录到need中
        for(int i = 0;i<t.length();i++){
            need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1);
        }
        int left=0,right=0; // 滑动窗口的边界
        int valid = 0; //窗口中满足need条件的字符个数
		
        //找到最右边
        while(right<s.length()){
            //c是即将移入窗口的字符
            Character c = s.charAt(right);
            //增加right指针扩大窗口
            right++;
            // 进行窗口内数据的更新
            ...
			/**
			如果当前c是窗口需要的 则添加进窗口
			对window进行操作
			*/
			
            //需要收缩窗口
            while(收缩窗口的条件){
                //答案可能更新的位置1
                ...

                //d是即将移出窗口的字符
                Character d = s.charAt(left);
                //增加left指针缩小窗口
                left++;
                // 进行窗口的更新
	            ...
				/**
				对window进行操作
				*/				
                //答案可能更新的位置w
                ...
            }
        }
 

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

扩张窗口时（right++）如何更新窗口数据
收缩窗口的条件
收缩窗口时（left–）如何更新窗口数据
一般收缩和扩张更新数据都是对应的
注意更新答案的地方：
明确我们需要的答案在哪部分，例如3.无重复最长子串，我们需要的答案就是在收缩完窗口才保证窗口内没有重复的串，这时更新答案最合适

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”

示例 2：
输入：s = “a”, t = “a”
输出：“a”

提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

思路：

当扩大窗口的时候，如果即将移入窗口的字符包含在need中，我们就要对window进行更新，更新后如果window里该字符的数量已经满足需求即和need中该字符的数量相等，valid就要++；
当已经找到可行解，即valid的值和need值相等就要开始收缩窗口
收缩窗口时，首先如果当前len比之前的len更小则更新len；然后就是对window进行更新，更新前如果window里该字符的数量已经满足需求即和need中该字符的数量相等，valid就要–；

需要注意的是，我们判断wind和need中字符个数不能用==而要用equals，因为我们定义的Map里的Integer是对象，Integer会缓存频繁使用的数值[-128,127]，超过此范围就会new一个对象，导致使用“==”错误

class Solution {
    public String minWindow(String s, String t) {

        HashMap<Character,Integer> need = new HashMap<Character, Integer>();//need 是需要凑齐的字符
        HashMap<Character,Integer> window = new HashMap<Character, Integer>(); // window是窗口中的字符
        // 把t中 每个字符出现的次数记录到need中
        for(int i = 0;i<t.length();i++){
            need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1);
        }
        int left=0,right=0; // 滑动窗口的边界
        int valid = 0; //窗口中满足need条件的字符个数
        int start = 0,len = Integer.MAX_VALUE; //最小覆盖子串的起始索引和长度
        //找到最右边
        while(right<s.length()){
            //c是即将移入窗口的字符
            Character c = s.charAt(right);
            //增加right指针扩大窗口
            right++;
            // 进行窗口内数据的更新
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            //需要收缩窗口： window里已经包含了t中所有字符，即找到了可行解，接下来找最优解
            while(valid==need.size()){
                //当前满足条件的最小子串 的长度比之前小 则更新
                if((right-left)<len){
                    start = left;
                    len = right-left;
                }

                //d是即将移出窗口的字符
                Character d = s.charAt(left);
                //增加left指针缩小窗口
                left++;
                // 进行窗口的更新
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

排列相关

字符串排列
找到字符串中所有字母异位词
这两道题几乎是一样的

567. 字符串排列

567. 字符串排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例 1：
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例 2：

输入: s1= “ab” s2 = “eidboaoo”
输出: False

提示：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

思路：
这道题的特点是找到最小的排列，那么我们收缩窗口的条件应该是当前窗口的长度大于等于s1的长度
返回true的条件就是valid和need的长度相等

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        HashMap<Character,Integer> need = new HashMap<Character,Integer>();
        HashMap<Character,Integer> window = new HashMap<Character,Integer>();
        for(int i=0;i<s1.length();i++){
            Character c = s1.charAt(i);
            need.put(c,need.getOrDefault(c,0)+1);
        }
        
        
        int left=0,right=0;
        int valid = 0; //满足条件的字符个数
        while(right<s2.length()){
            //即将移入窗口的字符
            Character q = s2.charAt(right);
            right++;
            //进行窗口内数据的更新
            if(need.containsKey(q)){
                window.put(q,window.getOrDefault(q,0)+1);
                if(need.get(q).equals(window.get(q))){
                    valid++;
                }
            }

            // 需要收缩窗口: 由于是排列，所以窗口大小比s1大的时候就需要收缩
            while(right-left>=s1.length()){
                if(valid==need.size()){ //符合条件
                    return true;
                }
                // d是即将移出窗口的字符
                Character d = s2.charAt(left);
                left++;
                if(need.containsKey(d)){
                    if(need.get(d).equals(window.get(d))){
                        valid--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }


        }
        return false;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:

输入:
s: “cbaebabacd” p: “abc”

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。
示例 2:

输入:
s: “abab” p: “ab”

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词。

思路：
和上一题是一样的，只不过需要用一个List来存所有满足条件的答案

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        
        HashMap<Character,Integer> need = new HashMap<Character,Integer>();
        HashMap<Character,Integer> window = new HashMap<Character,Integer>();
        List<Integer> ans = new ArrayList<>();
        for(int i = 0;i<p.length();i++){
            Character c = p.charAt(i);
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        int valid = 0;
        while(right<s.length()){
            Character q = s.charAt(right);
            right++;
            //更新窗口数据
            if(need.containsKey(q)){
                window.put(q,window.getOrDefault(q,0)+1);
                if(need.get(q).equals(window.get(q))){
                    valid++;
                }
            }

            //收缩窗口
            while(right-left>=p.length()){
                // 看当前窗口符合不符合答案
                if(valid==need.size()){
                    ans.add(left);
                }
                Character d = s.charAt(left);
                left++;
                if(need.containsKey(d)){
                    if(need.get(d).equals(window.get(d))){
                        valid--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }                

            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。
示例 4:

输入: s = “”
输出: 0

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

思路：
这道题是求无重复最长子串，所以我们扩张窗口时就将window的key+1。
收缩窗口的条件就是遇到重复的key(window里此key的值大于1).
注意更新答案是在收缩窗口结束后，因为我们需要的是最长无重复子串，保证窗口中的子串没有重复就是收缩完窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {

        HashMap<Character,Integer> window = new HashMap<Character,Integer>();
        int left=0,right=0;
        int len = 0;
        while(right<s.length()){
            Character c = s.charAt(right);
            right++;
            //更新窗口数据
            window.put(c,window.getOrDefault(c,0)+1);
            

            //收缩窗口：包含重复的key
            while(window.get(c)>1){
                Character d = s.charAt(left);
                left++;
                //更新窗口数据
                if(window.containsKey(d)){
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
            len = Math.max(len,right-left);
        }
        return len;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

904. 水果成篮

904. 水果成篮
在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：

把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。

你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。

用这个程序你能收集的水果树的最大总量是多少？

示例 1：
输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。

示例 2：
输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2]
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。

示例 3：
输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2]
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。

示例 4：
输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2]
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 棵水果树。

提示：
1 <= tree.length <= 40000
0 <= tree[i] < tree.length

思路：

窗口的个数大于2 也就是篮子装不下了
注意收缩时更新窗口的时候，要是当前key是0，要把它remove。

更新答案的地方是在收缩窗口结束后，因为这时窗口中是两种类型，即满足我们只有两个篮子的条件

class Solution {
    public int totalFruit(int[] tree) {

        HashMap<Integer,Integer> window = new HashMap<Integer,Integer>();
        int left=0,right=0;
        int res = 0;
        while(right<tree.length){
            //即将进入窗口的水果类型
            int type = tree[right];
            right++;
            //更新窗口数据
            window.put(type,window.getOrDefault(type,0)+1);

            //收缩窗口： 窗口的个数大于2 也就是篮子装不下了
            while(window.size()>2){
                int d = tree[left];
                left++;
                //更新窗口数据
                window.put(d,window.getOrDefault(d,0)-1);
                if(window.get(d)==0){
                    window.remove(d);
                }
            }
            //此时 窗口中有两种类型，可以更新答案 
            res = Math.max(res,right-left);

        }
        return res;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

固定窗口

此类题的窗口都是固定长度的
第一步：将初始窗口压满，得到初始值
第二步：从左向右滑动窗口，每向右滑动一次则添加一个元素，删除一个元素

567 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

示例 1：
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).

示例 2：
输入：s1= “ab” s2 = “eidboaoo”
输出：false

提示：
1 <= s1.length, s2.length <= 10⁴
s1 和 s2 仅包含小写字母

解析：

s2包含s1的排列，所以窗口的长度一定等于s1的长度，我们只需要用s1长度的窗口从左到右滑动即可，只要need和window的字母个数都一样则返回true。
s1和s2仅包含小写字母，直接用26个字母数组来存储

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()){
            return false;
        }
        int l1 = s1.length();
        int l2 = s2.length();
        int[] need = new int[26];
        for (int i=0;i<l1 ;i++){
            need[s1.charAt(i)-'a']++;
        }
        int[] window = new int[26];
        for (int i=0;i<l1 ;i++){
            window[s2.charAt(i)-'a']++;
        }
        if(check(need, window)){
            return true;
        }
        // 滑动固定窗口
        for (int i=l1;i<l2;i++){
            window[s2.charAt(i)-'a']++;
            window[s2.charAt(i-l1)-'a']--;
            if(check(need, window)){
                return true;
            }
        }
        return false;
    }

    public boolean check(int[] need, int[] window){
        for (int i=0;i<26;i++){
            if (need[i]!=window[i]){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

643. 子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10⁻⁵ 的答案都将被视为正确答案。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

提示：

n == nums.length
1 <= k <= n <= 10⁵
-10⁴ <= nums[i] <= 10⁴

    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        // 初始化最左窗口
        double sum = 0.0;
        for (int i = 0;i<k;i++){
            sum+=nums[i];
        }
        double max =sum;
        // 从左到右滑动窗口
        for (int i=1;i<=n-k;i++){
            sum = sum+nums[i+k-1]-nums[i-1];
            max = Math.max(max,sum);
        }
        return max/k;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

串联所有单词的子串：【刷穿LC】朴素哈希表解法 + 滑动窗口解法
子数组最大平均数 I：滑动窗口裸题（含模板）~
可获得的最大点数：详解滑动窗口基本思路（含模板）~

1423. 可获得的最大点数

几张卡牌排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例 1：

输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5
= 12 。

示例 2：

输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。

示例 3：
输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

示例 4：
输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。

示例 5：
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202
提示：
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

思路：要左右两边拿的k张最大，也就是不被拿的n-k张最小，这样就可以用上面的模板来解题了

class Solution {
    public int maxScore(int[] cardPoints, int k) {

        // 求n-k张的总和最小
        int n = cardPoints.length;
        int m = n-k;
        int sum = 0;
        int all = 0;
        // 总和
        for (int i=0;i<n;i++){
            all+=cardPoints[i];
        }
        // 初始化窗口
        for (int i=0;i<m;i++){
            sum+=cardPoints[i];
        }
        int min = sum;
        // 从左到右移动
        for (int i=m;i<n;i++){
            sum+=cardPoints[i]-cardPoints[i-m];
            min = Math.min(min,sum);
        }
        return all-min;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

单调队列解决滑动窗口问题

labuladong单调队列
对于找窗口中的最大值问题，我们可以维护一个单调队列，保证队列的首部一定为队列中的最大值，这样我们求当前窗口的最大值直接取队首元素即可。
维护单调队列：
push的时候需要把比自己小的全都删掉

    class MonotonicQueue{
        LinkedList<Integer> maxq = new LinkedList<>();
        public int max(){
            return maxq.getFirst();
        }
        // 单调队列的队首元素永远 保持是最大值。 在push的时候要把比自己小的都删除
        public void push(int n){
            while (!maxq.isEmpty() && maxq.getLast()<n){
                maxq.pollLast();
            }
            maxq.addLast(n);
        }
        public void pop(int n){
            if (n==maxq.getFirst()){
                maxq.pollFirst();
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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]

class Solution {
    class MonotonicQueue{
        LinkedList<Integer> maxq = new LinkedList<>();
        public int max(){
            return maxq.getFirst();
        }
        // 单调队列的队首元素永远 保持是最大值。 在push的时候要把比自己小的都删除
        public void push(int n){
            while (!maxq.isEmpty() && maxq.getLast()<n){
                maxq.pollLast();
            }
            maxq.addLast(n);
        }
        public void pop(int n){
            if (n==maxq.getFirst()){
                maxq.pollFirst();
            }
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 单调队列
        MonotonicQueue queue = new MonotonicQueue();
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        int left=0,right=0;
        while(right<n){
            if (right<k-1){
                queue.push(nums[right]);
                right++;
            }else{
                queue.push(nums[right]);
                res.add(queue.max());
                queue.pop(nums[left]);
                left++;
                right++;
            }
        }
        int []resArray = new int[res.size()];
        for (int i=0;i<res.size();i++){
            resArray[i] = res.get(i);
        }
        return resArray;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/490523