JavaScript滑动窗口最大值：从暴力法到单调队列详解

题目背景

给定一个整数数组 nums 和一个滑动窗口的大小 k，需要找出所有滑动窗口里的最大值。例如，当输入 nums = [1,3,-1,-3,5,3,6,7] 且 k = 3 时：

滑动过程如下：

• [1, 3, -1] -3 5 3 6 7 → 最大值 3
• 1 [3, -1, -3] 5 3 6 7 → 最大值 3
• 1 3 [-1, -3, 5] 3 6 7 → 最大值 5
• 1 3 -1 [-3, 5, 3] 6 7 → 最大值 5
• 1 3 -1 -3 [5, 3, 6] 7 → 最大值 6
• 1 3 -1 -3 5 [3, 6, 7] → 最大值 7

最终输出结果为：[3, 3, 5, 5, 6, 7]。

常见误区：暴力遍历法

初学者通常的第一反应是使用长度为 k 的临时数组或切片，每次滑动后重新计算最大值并加入结果集。具体步骤包括确定滑动次数为 nums.length - k + 1，初始化结果数组，然后在循环中截取子数组、求最大值并推进索引。

JavaScript 暴力实现示例：

var maxSlidingWindow = function(nums, k) {
    if (nums.length == 0 || k > nums.length) return [];
    var index = k;
    var len = nums.length - k + 1;
    var stack = [], res = [];
    // 初始化第一个窗口
    for (var j = 0; j < k; j++) {
        stack.push(nums[j]);
    }
    for (let i = 0; i < len; i++) {
        if (i !== 0) {
            stack.shift(); // 移除窗口左侧元素
            stack.push(nums[index++]); // 添加新元素
        }
        // 关键瓶颈：每次遍历整个窗口找最大值
        res.push(Math.max.apply(null, stack));
    }
    return res;
};

虽然逻辑直观，但该方法的单次最大值查找时间复杂度为 O(k)，整体循环 N-k+1 次，导致总时间复杂度达到 O(N×K)。在数据量较大时，极易触发“超出时间限制”错误。

最优解法：单调递减队列

为了将效率提升至线性时间 O(N)，我们需要一种能即时提供当前窗口最大值的数据结构。**单调递减双端队列**是解决此类问题的核心工具。队列中存储的是数组元素的**下标**（或值，但存下标便于判断过期），保证队列中的元素从队头到队尾始终呈现**递减**趋势。

算法核心逻辑

我们可以将整个过程拆解为以下三个关键动作：

1. 维护单调性（入队处理）： 每当遇到一个新元素，将其与队尾元素比较。如果新元素大于等于队尾元素，说明队尾元素不可能再成为后续窗口的最大值（因为新元素更大且存活时间更长），因此不断弹出队尾，直到队列为空或队尾元素大于新元素。最后将新元素（或其下标）加入队尾。
2. 剔除过期元素（队头检查）： 随着窗口向右滑动，队列最左边的元素（下标最小）可能会移出当前窗口范围。如果队头元素的下标小于当前窗口的左边界（即 i - k + 1），则将其移除。
3. 记录结果： 当窗口完全形成（即索引 i ≥ k-1）后，队头元素始终是当前窗口的最大值，直接存入结果数组。

JavaScript 实现细节

在实际编码中，使用数组模拟双端队列即可。push 用于入队，pop 用于从尾部出队，shift 用于从头部出队。

var maxSlidingWindow = function(nums, k) {
    const res = []; // 保存滑动窗口的最大值
    const q = [];   // 单调递减队列，存储数组下标
    
    for (let i = 0; i < nums.length; i++) {
        // 1. 维持单调递减性质
        // 如果新元素比队尾对应的值大，则队尾不可能是最大值，弹出队尾
        while (q.length > 0 && nums[i] > nums[q[q.length - 1]]) {
            q.pop();
        }
        // 将当前下标加入队尾
        q.push(i);
        
        // 2. 移除已经滑出窗口的队头元素
        // 当前窗口范围为 [i-k+1, i]，若队头下标小于左边界，则失效
        if (q[0] <= i - k) {
            q.shift();
        }
        
        // 3. 当窗口大小达到k时，开始记录结果
        if (i >= k - 1) {
            res.push(nums[q[0]]); // 队头即为当前窗口最大值
        }
    }
    return res;
};

此实现中，每个元素最多入队和出队一次，因此时间复杂度严格为 O(N)，空间复杂度为 O(K)，非常适合处理大规模数据。

小结

滑动窗口类问题中，构造单调队列是高频考点。单调递减队列能够确保在任何时刻，队首元素都是当前区间的极值。掌握“保持单调性”和“剔除过期值”这两个步骤，即可高效解决最大值/最小值查询问题。以上就是JavaScript日拱算法题解滑动窗口的最大值示例的详细内容，更多关于JavaScript 滑动窗口最大值的资料请关注本站其它相关文章！