292. 滑动窗口最大值

题目链接：https://leetcode-cn.com/problems/sliding-window-maximum

思路：我们可以用一个「双端队列」，有一个数组window来记录元素「下标」，遍历数组，宗旨就是在每次窗口滑动后，window的第一个元素记录着当前窗口最大元素的「下标」。首先，如果window中第一个元素记录的下标出了窗口的「左边界」，就把window的第一个元素移出。窗口中新进一个元素：

• 如果「新元素」比window中队尾元素的对应的值小，则直接把该「新元素」的下标放入window
• 如果「新元素」比window中队尾元素的对应的值大，则从「队尾」遍历，把比「新元素」小的元素的「下标」从window中移出。
• 上述操作就是为了保证每次窗口中，window的第一个元素对应的数值就是最大的。

代码：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    if( nums.length === 0 ) return [];
    let window = [];    // 用于存储nums数组下标
    let result = [];    // 用于输出结果
    for(let i = 0; i < nums.length; i++) {
        if(i >= k && window[0] <= i - k) window.shift();

        while(window && nums[window[window.length - 1]] <= nums[i]) {
            // 一直从队列尾部开始遍历，如果比当前新进元素小，则移出队列
            window.pop();
        }

        window.push(i);

        if(i >= k - 1) {
            result.push(nums[window[0]]);
        }
    }
    return result;
};