AC第四天

解题技巧：定长滑窗问题

定长滑窗问题通常可以通过以下步骤解决：

  1. 初始化窗口统计量

    • 定义一个变量来记录窗口内的统计量（如和、计数等）。
    • 初始化窗口的统计量，通常是前 k 个元素的统计值。

  2. 滑动窗口遍历数组

    • 使用一个循环，从第 k 个元素开始遍历数组。
    • 在每次迭代中，执行以下三步操作：
      • 入：将当前元素加入窗口，更新统计量。
      • 更新：根据当前窗口的统计量，更新答案（如最大值、最小值、计数等）。
      • 出：移除窗口左端的元素，更新统计量。

  3. 边界条件处理

    • 确保数组长度大于或等于窗口大小 k。
    • 根据题目要求，处理特殊情况（如空数组、无解等）。

  4. 优化

    • 使用滑窗技术避免重复计算，确保时间复杂度为 O(n)。

模板代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int solveSlidingWindow(int[] nums, int k) {
     int n = nums.length;
     int result = 0; // 根据题目需求初始化答案
     int windowSum = 0; // 窗口统计量

     // 初始化窗口
     for (int i = 0; i < k; i++) {
          windowSum += nums[i];
     }
     result = Math.max(result, windowSum); // 更新答案

     // 滑动窗口
     for (int i = k; i < n; i++) {
          windowSum += nums[i]; // 入
          windowSum -= nums[i - k]; // 出
          result = Math.max(result, windowSum); // 更新
     }

     return result;
}

适用场景：

  • 求定长子数组的最大/最小值。
  • 统计满足条件的定长子数组个数。
  • 计算定长子数组的平均值或其他统计量。

通过掌握滑窗的“入-更新-出”三步法，可以高效解决这类问题。

1.定长子串中元音的最大数目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
package com.nianxi;

import org.junit.jupiter.api.Test;

public class LeetCode12Test {
    @Test
    public void test(){
        String s = "abciiidef";
        int k = 3;
        System.out.println(maxVowels(s,k));
    }

    public int maxVowels(String s, int k) {
        char[] ch = s.toCharArray();
        int maxCount = 0;
        int temp = 0;
        for (int i = 0; i < s.length(); i++) {
            if (ch[i] == 'a' || ch[i] == 'e' || ch[i] == 'i' || ch[i] == 'o' || ch[i] == 'u'){
                temp++;
            }
            if (i <= k - 2){
                continue;
            }
            if (maxCount < temp){
                maxCount = temp;
            }
            char out = ch[i-k+1];
            if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u'){
                temp--;
            }
        }
        return maxCount;
    }
}

2.子数组最大平均数 ILeetCode

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
package com.nianxi;

import org.junit.jupiter.api.Test;

public class LeetCode13Test {
    @Test
    public void test() {
        int[] nums = {-1};
        int k = 1;
        System.out.println(findMaxAverage(nums,k));
    }

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

3.大小为 K 且平均值大于等于阈值的子数组数目 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
package com.nianxi;

import org.junit.jupiter.api.Test;

public class LeetCode14Test {
    @Test
    public void text() {
        int[] arr = {2,2,2,2,5,5,5,8};
        int k = 3;
        int threshold = 4;
        System.out.println(numOfSubarrays(arr,k,threshold));
    }

    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int count = 0;
        int sum = 0;
        int average;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (i < k - 1){
                continue;
            }
            average = sum / k;
            if (average >= threshold) {
                count++;
            }
            sum -= arr[i-k+1];
        }
        return count;
    }
}

4.半径为 k 的子数组平均值 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
package com.nianxi;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class LeetCode15Test {
    @Test
    public void test() {
        int[] nums = {7,4,3,9,1,8,5,2,6};
        int k = 3;
        System.out.println(Arrays.toString(getAverages(nums,k)));
    }
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            if (i < 2 * k) {
                continue;
            }
            ans[i - k] = (int) (sum / (2 * k + 1));
            sum -= nums[i - 2 * k];
        }
        return ans;
    }
}

5.得到 K 个黑块的最少涂色次数 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
package com.nianxi;

import org.junit.jupiter.api.Test;

public class LeetCode16Test {
    @Test
    public void test() {
        String blocks = "WBBWWBBWBW";
        int k = 7;
        System.out.println(minimumRecolors(blocks, k));
    }

    public int minimumRecolors(String blocks, int k) {
        char[] s = blocks.toCharArray();
        int cntW = 0;
        for (int i = 0; i < k; i++) {
            cntW += s[i] & 1;
        }
        int ans = cntW;
        for (int i = k; i < s.length; i++) {
            cntW += (s[i] & 1) - (s[i - k] & 1);
            ans = Math.min(ans, cntW);
        }
        return ans;
    }
}