滑动窗口在算法中的应用

滑动窗口是一种经典的算法技巧，就像在处理一系列动态数据时，用一扇可以滑动的“窗口”来捕捉一段连续的子数组或子字符串。通过不断地移动窗口的起点或终点，我们能够以较低的时间复杂度来解决一系列问题。在这篇文章中，我们将通过几个经典的 LeetCode 题目，使用 Java 语言来详细讲解滑动窗口的应用。

例题1：找到字符串中的所有异位词

题目背景：

朋友小明在编程比赛中遇到了一个问题：如何在一个长字符串中找到所有与目标字符串异位的子串？我们需要通过滑动窗口找到所有这些位置。

题目描述：

给定两个字符串 s 和 p，找出 s 中所有 p 的异位词的起始索引。字符串仅包含小写字母，并且 p 和 s 的长度都不超过 20,000。

示例：

输入: s = "cbaebabacd", p = "abc"
输出: [0, 6]

代码实现：

import java.util.*;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;

        int[] pCount = new int[26];  // 记录字符串 p 中字符的频率
        int[] sCount = new int[26];  // 记录当前窗口中字符的频率

        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }

        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            sCount[s.charAt(right) - 'a']++;
            
            // 如果窗口大小大于 p 的长度，收缩窗口
            if (right - left + 1 > p.length()) {
                sCount[s.charAt(left) - 'a']--;
                left++;
            }

            // 判断窗口内的字符频率与 p 是否一致
            if (Arrays.equals(sCount, pCount)) {
                result.add(left);
            }
        }
        
        return result;
    }
}

分析：

• 我们维护了两个频率表 pCount 和 sCount，分别用于记录字符串 p 的字符频率和当前窗口的字符频率。
• 时间复杂度为 O(n)，其中 n 是字符串 s 的长度。

例题2：水果成篮

题目背景：

我们去果园摘水果，朋友们想知道，如何在一个果树排列中，找到最长的连续子集，使得我们可以只用两个篮子装下这些水果。

题目描述：

在一排树中，第 i 棵树上有 tree[i] 型号的水果。你可以选择两个篮子，每个篮子只能装一种型号的水果。你需要找到可以采摘的水果的最大数量。

示例：

输入: tree = [1,2,1,2,1,3,3,4,3]
输出: 4

代码实现：

import java.util.*;

public class Solution {
    public int totalFruit(int[] tree) {
        Map<Integer, Integer> basket = new HashMap<>();
        int left = 0, maxFruit = 0;

        for (int right = 0; right < tree.length; right++) {
            basket.put(tree[right], basket.getOrDefault(tree[right], 0) + 1);

            // 如果篮子里有超过两种水果，开始收缩窗口
            while (basket.size() > 2) {
                basket.put(tree[left], basket.get(tree[left]) - 1);
                if (basket.get(tree[left]) == 0) {
                    basket.remove(tree[left]);
                }
                left++;
            }

            // 记录当前窗口的最大长度
            maxFruit = Math.max(maxFruit, right - left + 1);
        }

        return maxFruit;
    }
}

分析：

• 这里我们使用 HashMap 来记录当前窗口中的水果种类和数量。
• 当种类超过两个时，开始通过移动左指针缩小窗口，直到只剩下两种水果。
• 时间复杂度为 O(n)，空间复杂度为 O(1)。

例题3：最长重复字符替换

题目背景：

小丽正在玩一个文字游戏，要求她通过最多 k 次字符替换，将字符串中的一段字符变成相同的字符。她希望找出其中能够获得最长重复字符子串的长度。

题目描述：

给你一个仅由大写英文字母组成的字符串 s，你可以最多将 k 个字符替换为任意字符，求在执行上述操作后，能够得到的最长重复字符的子串的长度。

示例：

输入: s = "AABABBA", k = 1
输出: 4

代码实现：

public class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];  // 记录窗口内字符的频率
        int maxCount = 0, maxLen = 0, left = 0;

        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'A']++;
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);

            // 如果当前窗口大小减去窗口中最多的字符数大于 k，收缩窗口
            if (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

分析：

• 通过 count 数组记录每个字符的出现频率，并通过 maxCount 来维护窗口中出现最多的字符数。
• 如果窗口的大小超过 k + maxCount，说明需要缩小窗口。
• 时间复杂度为 O(n)，因为我们只对每个字符遍历一次。

总结

滑动窗口在处理连续子数组或子字符串问题时展现了极大的灵活性。通过维护一个动态窗口，滑动窗口不仅能够帮助我们有效解决问题，还可以极大地优化时间复杂度。在这些例子中，我们用 Java 语言展示了滑动窗口在寻找异位词、最大水果采摘量、以及字符替换中的应用。滑动窗口算法的威力在于，它不仅高效，而且能够适应各种复杂的题目。