滑动窗口和双指针II

发表于 2022-04-22 分类于算法思想本文字数： 5.1k 阅读时长 ≈ 5 分钟

滑动窗口与双指针 II

滑动窗口 1：同向交替移动的两个变量

子数组最大平均数 I
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
1
2
3
4
5
示例：
输入：[1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
思路：
事实上，相邻的两个长度固定的连续子数组，它们有一部分是重合的，在计算平均数的时候可以不用遍历。
由于窗口的长度固定，我们可以计算出所有的长度固定的连续子数组的和，在这些和中求出最大值，除以 k，就是题目要求的最大平均值。

代码如下：

public class Solution {

    public double findMaxAverage(int[] nums, int k) {
    	int len = nums.length ;
    	// 由于题目限制了 k <= len，因此不用做特判
    	int windowSum = 0;
    	for(int i = 0;i < k;i++){
    		windowSum += nums[i];
    	}
    	int res = windowSum;
    	// 循环不变量定义：[left..right) 是长度为 k 的窗口
    	for(int r = k; r < len;r++){
    		// 加上一个数再减去一个数
    		windowSum = windowSum + nums[r] - nums[r-k];
    		res = Math.max(res, windowSum);
    	}
    	return (double) res/k ;
    }
}

爱生气的书店老板

今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。请你返回这一天营业下来，最多有多少客户能够感到满意的数量。

示例：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

思路：

如果 grumpy[i] = 0 表示在这个时刻进店的顾客本来就是满意的。书店老板即使发动技能，这部分的顾客也不会因此受到影响。那么真正受到影响的就是 grumpy[i] = 1 的那些顾客，因此：
能够满意的客户数量 = 老板是不是发动技能都满意的客户数量 + 老板发动技能可以让顾客满意的数量
其中老板发动技能可以让顾客满意的数量就是那些 grumpy[i] = 1 的那些顾客，为了求得这部分的区间和，我们可以使用「前缀和」技巧：输入数组区间 preSum[i] 表示 [0..i) 的和，区间 [i..j] 的和可以使用 preSum[j] - preSum[i - 1] ，请大家重点体会我们的定义为什么 preSum[i] 是左闭右开的，且为什么要数组开 len + 1 长度。

代码如下：

public class Solution {

    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int len = grumpy.length;
        // 前缀和 preSum[i] 表示 [0..i) 里因为老板生气而感到不开心的顾客数
        int[] preSum = new int[len+1];

        // 统计 1. 所有本来就不生气的顾客数量；2. 前缀和数组
        int orignCount = 0;
        for(int i = 0 ;i<len ;i++){
        	if(grump[i] == 0){
        		//不生气
        		orignCount += customers[i];
        		preSum[i+1] = preSum[i];
        	}else {
        		// 生气时候的前缀和
        		preSum[i+1] = preSum[i] + customers[i];
        	}
        }

        int maxAngryCount = 0;
        // 固定长度的滑动窗口的左边界：[i..i + X)
        for(int l =0 ; l<len-X+1 ;l++){
        	maxAngryCount = Math.max(maxAngryCount, preSum[l+X]-preSum[l]);
        }
        // 所有本来就不生气的顾客
        return originCount + maxAngryCount ;
    }
}

滑动窗口 2：不定长度的滑动窗口

有一类数组上的问题，需要使用两个指针变量（我们称为左指针和右指针），同向、交替向右移动完成任务。这样的过程像极了一个窗口在平面上滑动的过程，因此我们将解决这一类问题的算法称为「滑动窗口」问题。
写对「滑动窗口」除了要弄清楚为什么可以使用滑动窗口，还需要明白代码编写过程中的「循环不变量」，这样才不会在初始化和一些边界问题上出错。

最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
1
2
3
4
示例：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC

思路：

一开始的时候，left 和 right 都位于下标 0 的位置。right 向右移动，直至包含 T 的所有字母。由于我们要求的是最小子串，因此，以 left 开头的子串 [left..right + 1]、 [left..right + 2]、……、 [left..len - 1] 一定不符合要求，因此这些区间可以不用判断；
然后考虑 left 如何移动。此时 left 不能向左移动，向左移动只能让子串更长，我们要求最小子串，因此 left 只能右移，移到恰恰好 [left..right] 区间里面的字符不包含 T 所有字母的最小子串；
然后 right 继续向右移动，直到包含 T 所有字母的最小子串。

重复这样的过程，直到 right 到达 S 的末尾。

那么如何判断区间 [left, right] 内包含 T 所有字母呢？由于我们并不关心字母的顺序，因此我们采用的是对比频数数组的方式。

  1. 先对 T 做频数统计，然后设置一个变量 distance 表示 T 中一共有多少个不同的字母；
  2. left 和 right 在动的时候，只对 T 中出现的字母做统计；
  3. right 移动的时候，频数增加，加到刚刚好和 T 对应字母相等的时候，distance - 1，表示滑动窗口内的字母种类与 T 的差距减少了 1，当这个差距为 0 的时候，滑动窗口内包含 T 所有字母的最小子串。此时考虑移动 left；
  4. left 移动的时候，做减法，减少到刚刚好比 T 中对应字符个数少 1 的时候，就说明「平衡」被打破，此时应该 right 继续向右移动。

  参考代码如下：
  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
54
55
56
public class Solution{
	public String minWindow(String s, String t) {
		int[] wins = new int[128];
		int[] patt = new int[128];

		final int A = 'A';

		for(Character c: t.toCharArray()){
			patt[c-A] ++;
		}
		int distance = 0;
		for(int i =0;i<128 ;i++){
			if(patt[i]>0){
				distance++;
			}
		}

		int slen =s.length();
		int start = 0;
		int left = 0;
		int right = 0;
		int match = 0 ;
		int minLen = slen+1;

		while(right<slen){
			Character curChar = s.charAt(right) ;
			if(patt[curChar - A] > 0){
				wins[curChar-A]++;

				if(wins[curChar - A] == patt[curChar - A]){
					match++;
				}
			}
			right++ ;

			while(match == distance){
				if(right - left<minLen){
					start = left ;
					minLen = right - left;
				}

				 // 考虑左边界向右边走
				Character leftChar = s.charAt(left);
				if(patt[leftChar - A] > 0){
					wins[leftChar - A]--;

					if(wins[leftChar - A] < patt[leftChar - A]){
						match --;
					}
				}
				left ++ ;
			}
		}
		return minLen == slen +1 ? "" : s.substring(start,start+minLen) ;
	}
}

替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

  示例：
   输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

思路：
使用 双指针（滑动窗口） ：

右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。

参考代码如下：

public class Solution {

 public int characterReplacement(String s, int k) {
 		int len = s.length();
 		if(len <2){
 			return len ;
 		}

 		char[] ch = s.toCharArray();
 		int l = 0;
 		int r = 0;

 		int res = 0;
 		int maxCount = 0;
 		int[] freq = new int[26];
 		// [left, right) 内最多替换 k 个字符可以得到只有一种字符的子串
 		while(r < len){
 			freq[ch[r] - 'A']++;
 			 // 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
 			maxCount = Math.max(maxCount, freq[ch[r] - 'A']) ;
 			r ++ ;

 			if(r-l > maxCount+k){
 			   // 说明此时 k 不够用
 			   // 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
 			   // 移出滑动窗口的时候，频数数组须要相应地做减法
 			   freq[ch[l] - 'A']-- ;
 			   l++;
 			}
 			res = Math.max(res , r-l);
 		}
 		return res ;
 	}
 }