快捷導航

Java實現(xiàn)滑動窗口算法的示例代碼

更新時間：2025年03月19日 08:45:21 作者：拾荒的小海螺

滑動窗口算法是一種高效解決子數(shù)組、子字符串問題的算法,廣泛應(yīng)用于數(shù)據(jù)流處理、網(wǎng)絡(luò)限流和字符串操作等場景,本文將詳細解析滑動窗口算法的核心思想、常見問題及其實現(xiàn)方式,需要的朋友可以參考下

1、簡述

滑動窗口算法是一種高效解決子數(shù)組、子字符串問題的算法，廣泛應(yīng)用于數(shù)據(jù)流處理、網(wǎng)絡(luò)限流和字符串操作等場景。本文將詳細解析滑動窗口算法的核心思想、常見問題及其實現(xiàn)方式，并結(jié)合具體示例和實際應(yīng)用場景進行說明。

2、核心思想

滑動窗口是一種雙指針技術(shù)，維護一個能夠在數(shù)據(jù)結(jié)構(gòu)上"滑動"的窗口（通常由兩個指針表示）。通過動態(tài)調(diào)整窗口的范圍，優(yōu)化計算的時間復雜度。

基本步驟：

初始化兩個指針 left 和 right，分別表示窗口的左邊界和右邊界。
移動 right 指針擴大窗口，直到窗口滿足問題的條件。
在滿足條件時，移動 left 指針縮小窗口，尋找更優(yōu)解或移除不必要的元素。
重復上述過程，直到 right 遍歷完整個數(shù)據(jù)結(jié)構(gòu)。

3、實踐樣例

以下是幾個經(jīng)典問題的滑動窗口解法：

3.1 找到字符串中所有不重復字符的最長子串

給定一個字符串，找出其中不含重復字符的最長子串。

import java.util.HashSet;

public class LongestSubstringWithoutRepeatingChars {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0, maxLength = 0;
        HashSet<Character> window = new HashSet<>();

        while (right < s.length()) {
            char c = s.charAt(right);
            if (!window.contains(c)) {
                window.add(c);
                maxLength = Math.max(maxLength, right - left + 1);
                right++;
            } else {
                window.remove(s.charAt(left));
                left++;
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestSubstringWithoutRepeatingChars solution = new LongestSubstringWithoutRepeatingChars();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); // Output: 3
    }
}

3.2 滑動窗口最大值

給定一個數(shù)組 nums 和一個大小為 k 的窗口，找到每個滑動窗口中的最大值。

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindowMaximum {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            // 移除窗口左側(cè)已過期的元素
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // 移除所有比當前元素小的元素，因為它們不會成為最大值
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // 當窗口達到大小 k 時，記錄最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        SlidingWindowMaximum solution = new SlidingWindowMaximum();
        int[] result = solution.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        for (int r : result) {
            System.out.print(r + " ");
        }
        // Output: 3 3 5 5 6 7
    }
}

4、應(yīng)用場景

滑動窗口算法因其高效性，在以下場景中應(yīng)用廣泛：

字符串處理：
查找字符串中的子串問題，例如最長無重復子串、包含所有指定字符的最短子串。
數(shù)據(jù)流處理：
在處理實時數(shù)據(jù)流時，通過滑動窗口維護最近的狀態(tài)，例如計算實時統(tǒng)計信息（平均值、最大值等）。
網(wǎng)絡(luò)限流：
滑動窗口用于實現(xiàn)動態(tài)限流算法，限制一段時間內(nèi)的請求數(shù)量。
數(shù)組處理：
處理固定窗口大小的問題，例如滑動窗口最大值、最小值等。