滑动窗口思想的介绍与单调队列代码实现

import java.util.Arrays;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        
        int n = nums.length;
        int[] res = new int[n - k + 1]; // 结果数组
        for (int i = 0; i <= n - k; i++) {
            int maxVal = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) {
                maxVal = Math.max(maxVal, nums[j]); // 计算窗口最大值
            }
            res[i] = maxVal;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        System.out.println(Arrays.toString(solution.maxSlidingWindow(nums, k)));
    }
}

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];

        int n = nums.length;
        int[] res = new int[n - k + 1]; // 结果数组
        Deque<Integer> deque = new ArrayDeque<>(); // 单调递减队列（存索引）

        for (int i = 0; i < n; i++) {
            // 1. 移除不在窗口范围的元素（左端越界）
            if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // 2. 维护队列单调递减（移除比当前值小的元素）
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }

            // 3. 添加新元素索引
            deque.addLast(i);

            // 4. 记录窗口最大值（窗口形成后才开始存结果）
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        System.out.println(Arrays.toString(solution.maxSlidingWindow(nums, k)));
    }
}

nums = {1, 3, -1, -3, 5, 3, 6, 7} 和滑动窗口大小 k = 3 来进行模拟。

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        int n = nums.size();
        long maxSum = 0;
        long sum = 0;
        // 哈希表记录窗口内元素的频次
        HashMap<Integer,Integer> hashMap = new LinkedHashMap<>();
        // 初始化前 k 个元素的窗口
        for(int i = 0;i<k;i++)
        {
            hashMap.put(nums.get(i),hashMap.getOrDefault(nums.get(i),0)+1);
            sum+=nums.get(i);
        }
        // 检查窗口是否符合“几乎唯一”条件
        if(hashMap.size()>=m)
        {
            maxSum = sum;
        }
        // 滑动窗口，窗口右移
        for(int i = k;i<n;i++)
        {
            // 移除窗口最左边的元素
            int left = nums.get(i-k);
            hashMap.put(left,hashMap.get(left)-1);
            if(hashMap.get(left)==0)
            {
                hashMap.remove(left);
            }
            sum-=left;
            // 添加窗口右边的新元素
            int right = nums.get(i);
            hashMap.put(nums.get(i),hashMap.getOrDefault(nums.get(i),0)+1);
            sum+=right;
            // 如果当前窗口包含至少 m 个不同的元素，更新最大和
            if(hashMap.size()>=m)
            {
                maxSum = Math.max(sum,maxSum);
            }
        }
        return maxSum;
    }
}

import java.util.HashMap;

class Solution {
    public int maximumLengthSubstring(String s) {
        // 哈希表，用于记录当前窗口内每个字符的出现次数
        HashMap<Character, Integer> charCount = new HashMap<>();
        
        int left = 0; // 滑动窗口的左边界
        int maxLength = 0; // 最长符合条件的子字符串的长度
        
        // 遍历字符串
        for (int right = 0; right < s.length(); right++) {
            // 更新当前字符的计数
            char currentChar = s.charAt(right);
            charCount.put(currentChar, charCount.getOrDefault(currentChar, 0) + 1);
            
            // 如果当前窗口内某个字符出现超过2次，移动左指针
            while (charCount.get(currentChar) > 2) {
                char leftChar = s.charAt(left);
                charCount.put(leftChar, charCount.get(leftChar) - 1);
                left++; // 移动左边界
            }
            
            // 计算当前窗口的长度并更新最大长度
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength; // 返回最长符合条件的子字符串的长度
    }
}