滑动窗口中的最大值

滑动窗口中的最大值 (opens new window)：

给你一个整数数组 nums，有一个大小为 k* *的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值。

本题的核心思想是维护一个单调队列，当滑动窗口开始滑动的时候，队列头部的元素就是当前滑动窗口中的最大值。

解题步骤：

1. 创建一个队列deque和结果数组result。
2. 遍历数组，然后按顺序执行以下步骤： a. 确保队列头部的元素依然处于滑动窗口中。 b. 确保加入队列的元素要比队列尾部的元素小，否则一直取出队列尾部元素，直到满足条件。 c. 将当前元素加入队列。 d. 在滑动窗口即将要滑动，也就是遍历到滑动窗口末尾的时候。收割结果，将队列头部元素加入到结果数组中。

var maxSlidingWindow = function(nums, k) {
    const result = [];
    const deque = []; // 双端队列，存储窗口中的元素索引

    for (let i = 0; i < nums.length; i++) {
        // 确保队列头部元素仍然处于滑动窗口中
        if (deque.length > 0 && deque[0] <= i - k) {
            deque.shift()
        }
        // 确保队列递减
        while (deque.length > 0 && nums[i] >= nums[deque[deque.length - 1]]) {
            deque.pop()
        }
        deque.push(i)
        // i到达滑动窗口的最后一个数字的时候，将队列头部元素加入结果中。
        // 这一步会发生在第一个判断条件之前，不用担心结果无法被正确收割。
        if (i >= k - 1) {
            result.push(nums[deque[0]])
        }
    }
    return result;
};

关于这个步骤的记忆方法。首先我们需要明白加入队列中的每一个元素都需要进行审查，首先是确保加入这个元素不会导致滑动窗口滑动，也就是队列头部元素也就处于队列之中；其次还需要维护队列的单调性，即新元素都需要和队尾元素进行对比。完成这两步审查以后，元素才能被加入队列。最后，每一次加入新元素都可能导致滑动窗口的最大值发生变化，当遍历到的元素处于滑动窗口的尾部的时候，就要记录结果了。记录结果的过程一定是在元素经过审查加入队列之后发生的，因为新元素的加入可能导致滑动窗口中最大值发生变化。