LeetCode 补拙笔记

0. 前言

• 日期：2026.06.28
• 题目：239. 滑动窗口最大值
• 难度：困难
• 标签：单调队列、滑动窗口、数组

1. 题目理解

问题描述 给定数组 nums 和窗口长度 k，窗口每次向右滑动一格，求出每个窗口内的最大值，按滑动顺序返回结果数组。

示例

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]

2. 解题思路

核心观察

1. 原始代码：分两段循环处理首窗口与后续滑动窗口，队列存在冗余清理逻辑、多余分支，重复代码多；
2. 优化暴力跳跃查找方案：缓存上一轮最大值下标，若下标仍在当前窗口内，仅对比新右边界更新最大值；若最大值滑出窗口，则重新遍历当前窗口查找最大值；
3. 对比单调队列：优化方案省去双端队列容器，仅用变量缓存最值，空间开销更低，但极端递减数组会退化至 $O(nk)$。

算法步骤

1. 初始化左右指针、缓存最大值与对应下标；
2. 右指针走到窗口末尾，循环处理每个窗口：
   • 若缓存最大值下标仍在窗口内，仅用新增右侧元素更新最值；
   • 若缓存最大值滑出窗口，重新遍历当前窗口查找全局最大值；
   • 将当前窗口最大值存入结果数组；
   • 左右指针同步右移一格；
3. 窗口遍历完成，返回结果数组。

3. 代码实现

package lc239;

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

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int index = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < k; i++) {
            if (deque.isEmpty()) {
                deque.offer(i);
                continue;
            }
            while (!deque.isEmpty()&&deque.peekFirst() < index) {
                deque.removeFirst();
            }

            while (!deque.isEmpty()&&nums[i] > nums[deque.peekLast()]) {
                deque.removeLast();
            }
            deque.offer(i);
            while (!deque.isEmpty()&&nums[i] > nums[deque.peekFirst()]) {
                deque.removeFirst();
            }
        }
        res[index++] = nums[deque.peekFirst()];
        for (int i = k; i < n; i++) {
            while (!deque.isEmpty()&&deque.peekFirst() < index) {
                deque.removeFirst();
            }
            while (!deque.isEmpty()&&nums[i] > nums[deque.peekLast()]) {
                deque.removeLast();
            }
            deque.offer(i);
            while (!deque.isEmpty()&&nums[i] > nums[deque.peekFirst()]) {
                deque.removeFirst();
            }
            res[index++] = nums[deque.peekFirst()];
        }
        return res;
    }
}

4. 代码优化说明

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
    int left = 0;
    int right = k - 1;
    int maxVal = Integer.MIN_VALUE;
    int maxValIndex = -1;
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    // 滑动窗口主循环
    while (right < n) {
        // 缓存最大值下标仍在窗口内，仅比较新增右侧元素
        if (maxValIndex > left) {
            if (nums[right] > maxVal) {
                maxVal = nums[right];
                maxValIndex = right;
            }
        } else {
            // 最大值滑出窗口，完整遍历当前窗口重新找最大值
            maxVal = nums[left];
            maxValIndex = left;
            for (int j = left + 1; j <= right; j++) {
                if (nums[j] >= maxVal) {
                    maxVal = nums[j];
                    maxValIndex = j;
                }
            }
        }
        ans[left] = maxVal;
        left++;
        right++;
    }
    return ans;
}
}

5. 复杂度分析

• 原始单调队列版本 时间复杂度：$O(n)$，每个元素仅入队、出队一次；两段循环拆分，存在大量重复队列清理逻辑、多余if分支 空间复杂度：$O(k)$，双端队列最多存储窗口内k个下标
• 缓存最值优化版本 时间复杂度：平均 $O(n)$，极端单调递减数组退化至 $O(nk)$；移除队列容器，合并冗余清理逻辑，减少多层while分支 空间复杂度：$O(1)$，仅常数临时变量，无额外容器占用

6. 总结

• 核心：缓存上一窗口最大值下标，减少重复遍历窗口的开销；
• 优化亮点：舍弃双端队列，仅用基础变量缓存最值，降低空间占用；合并重复的队列清理循环，消除大量冗余分支；
• 取舍：平均效率优秀，但存在最坏时间退化；追求稳定线性时间优先使用单调队列解法。