LeetCode 239 滑动窗口最大值：单调队列解法

在滑动窗口的过程中，队列的头部始终是当前窗口的最大值。我们只需要在窗口滑动的过程中不断维护这个队列即可。

核心维护逻辑

维护队列主要关注两个点：

1. 移除过期元素：当新元素进入窗口时，如果队首元素的索引已经不在当前窗口范围内（即 index + k <= i），则需要将其弹出。
2. 维护单调性：在将新元素加入队列之前，需要从队尾开始比较。如果队尾元素小于等于当前元素，那么队尾元素就没有存在的必要了。因为当前元素更大且更新（存活时间更长），它会覆盖掉那些更老且更小的值。

注意，队列中存储的应该是元素的索引，而不是值本身，这样我们才能方便地判断元素是否超出了窗口范围。

代码实现

以下是基于 JavaScript 的实现，使用数组模拟双端队列：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const ans = [];
    // 初始化双端队列，存储索引
    const queue = [];

    // 处理前 k 个元素，构建初始窗口
    for (let i = 0; i < k; ++i) {
        // 维护队尾：去除比当前值小且旧的元素
        while (queue.length > 0 && nums[queue[queue.length - 1]] <= nums[i]) {
            queue.pop();
        }
        // 新元素入队
        queue.push(i);
    }
    
    // 第一个窗口的最大值
    ans.push(nums[queue[0]]);

    // 处理剩余元素
    for (let i = k; i < nums.length; ++i) {
        // 维护队尾：保持单调递减
        while (queue.length > 0 && nums[queue[queue.length - 1]] <= nums[i]) {
            queue.pop();
        }
        // 新元素入队
        queue.push(i);

        // 维护队首：移除超出窗口范围的索引
        while (queue.length > 0 && queue[0] + k <= i) {
            queue.shift();
        }

        // 队首即为当前窗口最大值
        ans.push(nums[queue[0]]);
    }

    return ans;
};

测试用例

// 输入：[9,10,9,-7,-4,-8,2,-6], k = 5
// 预期输出：[10,10,9,2]