^-^
I am who I am.
滑动窗口 - Sliding Window
最近更新：2024-07-18   |   字数总计：2.6k   |   阅读估时：10分钟   |   阅读量：次
  1. 基础算法 - 滑动窗口
    1. 相关题目
      1. 3. 无重复字符的最长子串 - 力扣（LeetCode）
      2. 76. 最小覆盖子串 - 力扣（LeetCode）
      3. 567. 字符串的排列 - 力扣（LeetCode）
      4. 438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
      5. 239. 滑动窗口最大值 - 力扣（LeetCode）

基础算法 - 滑动窗口

滑动窗口（Sliding Window）是一种高效的数组/字符串处理技术，常用于解决子数组或子字符串相关的问题。它通过在数组或字符串上维护一个固定大小的窗口或动态调整窗口的大小，来逐步遍历并处理每个子集。

滑动窗口的主要特点包括：

  • 固定窗口大小：在某些问题中，滑动窗口的大小是固定的，窗口从数组或字符串的一端滑动到另一端。
  • 动态调整窗口大小：在其他问题中，滑动窗口的大小是动态调整的，根据条件扩展或缩小窗口。
  • 高效处理子问题：滑动窗口技术通过在遍历过程中维护窗口状态，能够高效地解决许多子数组或子字符串问题。

滑动窗口通常用于解决以下类型的问题：

  • 最大/最小子数组和问题：寻找具有最大或最小和的子数组。
  • 子字符串问题：寻找包含某些字符或满足某些条件的最长或最短子字符串。
  • 计数问题：统计子数组或子字符串中满足特定条件的元素数量。

滑动窗口的实现步骤

  1. 初始化窗口的起始和结束位置：通常设置两个指针，分别表示窗口的起始和结束位置。
  2. 滑动窗口：根据问题的需求移动窗口的起始或结束位置，动态调整窗口大小。
  3. 更新状态：在滑动窗口的过程中，维护并更新窗口内的状态（如窗口内元素的和、计数等）。
  4. 处理结果：在滑动窗口的过程中或结束后，根据窗口内的状态处理最终结果。

滑动窗口是一种非常强大的技术，能够将许多原本需要嵌套循环解决的问题简化为线性时间复杂度，是解决大量数据处理问题的重要工具。

相关题目

3. 无重复字符的最长子串 - 力扣（LeetCode）

难度：中等

一开始我写出来的解法如下，用到了哈希表和滑动窗口。

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        int start = 0;
        int cur = start;
        int len = s.length();
        HashSet<Character> set = new HashSet<Character>();
        while(cur<len){
            char a = s.charAt(cur);
            if(set.contains(a)){
                // 如果cur所指的的字符串在前面已经出现过
               start ++;
               cur = start;
               set.clear();
            }else{
                set.add(a);
                cur++;
                // 指针后移一次就需要重新计算一下res是否要更新
                int tmp = cur - start;
                if(res < tmp) res = tmp;
            }
        }
        return res;
    }
}

我们的滑动窗口一旦遇到重复的，就会从下一个字母从头开始数，其实浪费了非常多的时间和资源。

所以这样的时间复杂度很高。

要优化，就要优化头部和尾部的滑动时机。

队列式滑动窗口，比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

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
class Solution {
    public int lengthOfLongestSubstring(String s){
        // 最终的结果
        int res = 0;
        // 字符串长度
        int len = s.length();
        // 哈希表
        HashSet<Character> map = new HashSet<Character>();
        // 模拟队列头
        int left = 0;
        // 模拟队列尾 初始队列长度为0
        int right = left;
        while(right<len){
            char cur = s.charAt(right);
            // 如果队列尾所指的字符不在hash表中，则将其加入哈希表，并且left++，然后再比较一下现在的队列的长度
            if(!map.contains(cur)){
                map.add(cur);
                right++;
                int tmp = right - left;
                if(res < tmp) res = tmp;
            }else{
                // 如果队列尾所指的字符串在hash表中，说明队列里面已经有重复的字符了，我们从队列的头部慢慢弹出字符
                do{
                    char head_char = s.charAt(left);
                    // 从hash表中移除head_char
                    map.remove(head_char);
                    // 队列头部指针要+1
                    left++;
                    // 弹出了那个重复的字母为止
                }while(map.contains(cur));
            }
        }
        return res;
    }
}

76. 最小覆盖子串 - 力扣（LeetCode）

难度：困难

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
50
51
52
53
class Solution {
    public String minWindow(String s, String t) {
        int s_len = s.length();
        int t_len = t.length();
        // 记录满足要求的字串的起始位置和长度
        int start = 0;
        int len = Integer.MAX_VALUE;
        // 记录t串的每一个字符
        int[] cnt = new int[128]; // 用于记录状态 cnt[tmp]的值如果是大于0的，那就表明还需要这个字符，如果是小于0的，就表示多余了这个字符
        int count = 0; // 表示匹配成功还需要多少个字符 当count=0的时候表示匹配成功
        for (int i = 0; i < t_len; i++) {
            char tmp = t.charAt(i);
            cnt[tmp]++;
            count++;
        }
        // 下面是滑动窗口的逻辑
        // 定义[right,left)为窗口
        int right = 0;
        int left = 0;
        while (right < s_len) {
            char tmp = s.charAt(right);
            right++;
            cnt[tmp]--;
            // 当cnt[tmp]满足>=0这个条件，表明tmp是一个被需要的字符
            if (cnt[tmp] >= 0) {
                // count代表还差多少个字符数 可以达到要求，所以这里-1，代表找到了一个满足的
                count--;
            }
            // 判断一下count是否等于0，如果等于0就需要慢慢缩小窗口了
            while (count == 0) {
                char tmp_ = s.charAt(left);
                // 表示去除了tmp_字符后，cnt数组中对应字符的计数应该+1，代表的意义为：将多余的铲除（将以前的负值颁正），但是如果不幸铲除了
                // 需要的字符，那么就会使得该字符所对应的数值大于0，这时就应该重新更新count的值了
                cnt[tmp_]++;
                if (cnt[tmp_] > 0) {
                    // 表示当前的这个字符如果被滑出，那么就会导致要求不满足，所以这里就是极限值
                    // 所以在这里就进行判断是否是最小的字串 ⭐
                    int len_tmp = right - left;
                    if (len_tmp < len) {
                        len = len_tmp;
                        start = left;
                    }
                    count++;
                }
                left++; // 窗口收缩⭐[滑掉这个无关或者有关的字符]
            }
        }
        if (len == Integer.MAX_VALUE)
            return "";
        else
            return s.substring(start, start + len);
    }
}

要注意窗口移动的细节。

567. 字符串的排列 - 力扣（LeetCode）

难度：中等

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
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // s1 s2的长度
        // s1是小串，s2是大串
        int len_1 = s1.length();
        int len_2 = s2.length();
        // 记录状态数
        int[] need = new int[128];
        int count = 0;
        for(int i=0;i<len_1;i++){
            char tmp = s1.charAt(i);
            need[tmp]++;
            count++;
        }
        // 滑动窗口部分
        int left = 0;
        int right = 0;
        while(right<len_2){
            char tmp = s2.charAt(right);
            right++;
            // 如果该字符是tmp需要的字符
            need[tmp]--;
            if(need[tmp]>=0){
                count--;
            }
            while(count==0){
                char tmp_ = s2.charAt(left);
                need[tmp_]++;
                if(need[tmp_]>0){
                    count++;
                    // LeetCode 76题的思路
                    // 在这里，left所指的字符是关键的字符，不能弹出
                    // 但是本题，我们不是要去求得 最小覆盖字符串 我们只需要判断是否是全排列中的一个就可以
                    // 所以只需要判断当前长度是不是len_2
                    if(len_1==(right-left))
                        return true;
                }
                left++;
            }
        }
        return false;
    }
}

和上一题是几乎一样的，不同点在于此题需要判断滑动窗口中的串是不是子串的排列之一，通过滑动窗口的长度判断即可。

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

难度：中等

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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        // 获得s和p串的长度
        int s_len = s.length();
        int p_len = p.length();
        // 记录状态
        int[] need = new int[128];
        int count = 0;
        // 初始化状态
        for(int i=0;i<p_len;i++){
            char tmp = p.charAt(i);
            need[tmp]++;
            count++;
        }
        // 滑动窗口
        int left=0;
        int right=0;
        while(right<s_len){
            char tmp = s.charAt(right);
            right++;
            need[tmp]--;
            if(need[tmp]>=0){
                count--;
            }
            while(count==0){
                char tmp_ = s.charAt(left);
                need[tmp_]++;
                // 如果这个条件满足，表示当前left所指的这个字符是至关重要的字符，少了它就要开始着眼于right了
                if(need[tmp_]>0){
                    count++;
                    // 如果长度相等那就是异位串,记录一下
                    if((right-left)==p_len)
                        res.add(left);
                }
                // left指针照常移动
                left++;
            }
        }
        return res;
    }
}

76 567 438 这三个题都可以使用同一个模板去解决。

239. 滑动窗口最大值 - 力扣（LeetCode）

难度：困难

最暴力解法如下，时间复杂度为(n*m)，必然会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] res = new int[len-k+1];
        // 暴力
        for(int i=0;i<len-k+1;i++){
            int tmp_max = Integer.MIN_VALUE;
            for(int j=i;j<i+k;j++){
                tmp_max=Math.max(nums[j],tmp_max);
            }
            res[i] = tmp_max;
        }
        return res;
    }
}

那么有没有什么可以减少时间复杂度的呢？

在暴力法中，获得新区间的最大值的方法是重新遍历一遍新区间，这使得时间复杂度变得高了，每一次寻找最大值的时间复杂度为O(k)

要降低复杂度，主要是： 在每次滑动窗口后，如何用O(1)的时间复杂度获取最大值

我们可以使用单调队列的方式来解决。

维护一个队列：使得这个队列中的元素全是当前窗口的元素，并且这些元素是单调递减的（队列头是最大的，依次递减）

每一个新的滑动窗口，只需要获取队列头的值就可以了

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
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 处理边界情况
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        int len = nums.length;
        int[] res = new int[len - k + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        
        for (int r = 0; r < len; r++) {
            // 计算左边界
            int l = r - k + 1;
            
            // 移除滑动窗口外的元素
            if (!queue.isEmpty() && queue.peekFirst() < l) {
                queue.removeFirst();
            }
            
            // 维护队列单调递减
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[r]) {
                queue.removeLast();
            }
            
            // 将当前元素的索引加入队列
            queue.addLast(r);
            
            // 当左边界大于等于0时，将队列头部的元素加入结果数组
            if (l >= 0) {
                res[l] = nums[queue.peekFirst()];
            }
        }
        
        return res;
    }
}

2024-06-08 该篇文章被 jay1an 打上标签: 基础算法 滑动窗口 归为分类: 基础算法

上一篇：回溯 - Backtracking 下一篇：双指针 - Two Pointers
© 1949-2024 Jay1an
从头努力也坎坷 本站由Hexo驱动｜使用Hexo-theme-A4主题