LeetCode 239. 滑动窗口最大值 - 最优算法实现

LeetCode 239. 滑动窗口最大值 - 最优算法实现

🎯 问题理解

给定数组 nums 和窗口大小 k，滑动窗口从左到右移动，返回每个位置窗口中的最大值。

关键挑战：如何在O(n)时间内高效维护滑动窗口的最大值？

💡 核心思路

使用双端队列(Deque)维护一个单调递减队列：

• 队列存储数组索引（非数值）
• 队头永远是当前窗口的最大值索引
• 保持队列从队头到队尾单调递减

💻 最简短代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 移除超出窗口范围的索引
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // 移除比当前元素小的所有索引
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
            
            // 当窗口形成时，记录最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

仅18行核心代码！

🎭 最易懂代码（注释版）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];  // 结果数组
        Deque<Integer> window = new ArrayDeque<>();  // 存储索引的双端队列
        
        for (int i = 0; i < n; i++) {
            // 步骤1：移除超出窗口左边界的索引
            if (!window.isEmpty() && window.peekFirst() < i - k + 1) {
                window.pollFirst();
            }
            
            // 步骤2：维护单调递减特性
            // 移除所有比当前元素小的索引（它们不可能成为最大值）
            while (!window.isEmpty() && nums[window.peekLast()] < nums[i]) {
                window.pollLast();
            }
            
            // 步骤3：添加当前元素索引
            window.offerLast(i);
            
            // 步骤4：当窗口大小达到k时，记录最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[window.peekFirst()];
            }
        }
        
        return result;
    }
}

🎬 可视化演示过程

示例1：nums = [1,3,-1,-3,5,3,6,7], k = 3

🔄 完整执行过程

🎯 逐步执行详解

i=0: 处理元素 nums[0]=1

当前状态：

i=1: 处理元素 nums[1]=3

当前状态：

i=2: 处理元素 nums[2]=-1

窗口1：[1, 3, -1] → 最大值 = nums[1] = 3

i=3: 处理元素 nums[3]=-3

窗口2：[3, -1, -3] → 最大值 = nums[1] = 3

i=4: 处理元素 nums[4]=5

窗口3：[-1, -3, 5] → 最大值 = nums[4] = 5

i=5: 处理元素 nums[5]=3

窗口4：[-3, 5, 3] → 最大值 = nums[4] = 5

i=6: 处理元素 nums[6]=6

窗口5：[5, 3, 6] → 最大值 = nums[6] = 6

i=7: 处理元素 nums[7]=7

窗口6：[3, 6, 7] → 最大值 = nums[7] = 7

📊 执行结果总结

最终结果：[3, 3, 5, 5, 6, 7] ✅

🧠 算法核心原理

💡 为什么使用双端队列？

1. 队头维护最大值：队头索引对应的元素永远是当前窗口最大值
2. 队尾处理新元素：新元素从队尾进入，移除比它小的无用元素
3. 单调递减特性：确保队列中元素从大到小排列

🔍 关键操作解析

1️⃣ 移除超出窗口的索引

while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
    deque.pollFirst();
}

• 目的：确保队列中索引都在当前窗口范围内
• 边界：i - k + 1 是窗口左边界

2️⃣ 维护单调递减特性

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
    deque.pollLast();
}

• 目的：移除比当前元素小的索引（它们不可能成为最大值）
• 原理：当前元素更新且索引更大，完全"支配"了较小的旧元素

3️⃣ 记录窗口最大值

if (i >= k - 1) {
    result[i - k + 1] = nums[deque.peekFirst()];
}

• 条件：窗口大小达到k
• 结果：队头索引对应的元素就是最大值

🎨 动画演示

队列状态变化图

初始: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i=0: [1]     → deque = [0]
i=1: [1,3]   → deque = [1]      (移除0，因为1 < 3)
i=2: [1,3,-1] → deque = [1,2]   (保留3，添加-1) → 结果: 3
i=3: [3,-1,-3] → deque = [1,2,3] (全部保留) → 结果: 3
i=4: [-1,-3,5] → deque = [4]     (移除1,2,3，因为都 < 5) → 结果: 5
i=5: [-3,5,3]  → deque = [4,5]   (保留5，添加3) → 结果: 5
i=6: [5,3,6]   → deque = [6]     (移除4,5，因为都 < 6) → 结果: 6
i=7: [3,6,7]   → deque = [7]     (移除6，因为6 < 7) → 结果: 7

🔧 完整测试代码

import java.util.*;

public class SlidingWindowMaximum {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 移除超出窗口范围的索引
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // 移除比当前元素小的所有索引
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
            
            // 当窗口形成时，记录最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        SlidingWindowMaximum solution = new SlidingWindowMaximum();
        
        // 测试用例
        int[][] testCases = {
            {1, 3, -1, -3, 5, 3, 6, 7}, // k=3 → [3,3,5,5,6,7]
            {1},                         // k=1 → [1]
            {1, -1},                     // k=1 → [1,-1]
            {9, 11},                     // k=2 → [11]
            {4, -2, -3, 4, -1, 2, 1, -5, 4} // k=4 → [4,4,4,4,2,4]
        };
        
        int[] kValues = {3, 1, 1, 2, 4};
        
        for (int i = 0; i < testCases.length; i++) {
            int[] nums = testCases[i];
            int k = kValues[i];
            int[] result = solution.maxSlidingWindow(nums, k);
            
            System.out.printf("输入: %s, k=%d%n", Arrays.toString(nums), k);
            System.out.printf("输出: %s%n%n", Arrays.toString(result));
        }
    }
}

⚡ 性能分析

• 时间复杂度：O(n) - 每个元素最多入队出队一次
• 空间复杂度：O(k) - 双端队列最多存储k个索引

🎯 关键记忆点

1. 存索引不存值：方便检查窗口边界
2. 单调递减队列：队头永远是最大值
3. 两端操作：队头移除过期，队尾维护单调性
4. 懒删除思想：不需要的元素自然被移除

💫 算法优势

1. 最优时间复杂度：O(n)线性时间
2. 代码简洁：核心逻辑仅18行
3. 思路清晰：单调队列经典应用
4. 空间高效：只需O(k)额外空间

这个算法完美体现了数据结构与算法设计的精妙结合！