前言

什么是队列？

队列是一种数据结构，用于存储数据元素，并按照先进先出（First In First Out，FIFO）的原则进行操作。在队列中，新元素在队尾添加，而旧元素从队头移除，类似于排队等候的过程，先到的元素先被处理，后到的元素排在后面等待处理。

正文

题目描述(力扣239)

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

返回 滑动窗口中的最大值 。 示例 1：

输入： nums = [1,3,-1,-3,5,3,6,7], k = 3
输出： [3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[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

解答

方法一

当碰到滑动窗口的应用时，我们应该想到用双指针来实现滑动窗口，定义两个指针，分别为left和right，两个指针之间的区间长度为k，left = 0，right = k - 1，通过滑动两个指针来滑动窗口，每次通过for循环来遍历得到目前窗口的最大值，并定义一个空数组res，每次将得到的最大值push到该数组，最后返回该数组。

var nums = [1,3,-1,-3,5,3,6,7], k = 3;
//窗口 -->双指针
var maxSlidingWindow = function(nums, k) {
 let left = 0, right =  k - 1;
 let res = [];
 while(right < nums.length){
    let max = nums[left];
    for (var i = left; i <= right; i++) {
     if(nums[i] > max) {
        max = nums[i];
     }
    }
    res.push(max);
    left++;  
    right++;
 }
return res;
};

console.log(maxSlidingWindow(nums, k));

但是要注意！！！这个方法超出了时间限制，所以我们要换一种方法，用队列来实现

方法二

定义一个队列queue，queue用于存数组的下标，通过for循环来遍历数组，再通过while来判断当前遍历到的数如果大于或者等于以队尾的数为下标的数，且此时队列非空，如果满足条件，就将队尾的数pop掉，直到满足以队尾为下标的数大于当前遍历的数为止，然后将当前遍历到的数push到队尾中，从而维护queue为一个递减队列；再通过一个while来流出值，来维持窗口的大小为k，如果超出滑动窗口长度，就将队头元素移除掉；再通过if来判断是否遍历完一个滑动窗口，并记录每个窗口的最大值，定义一个数组res，如果遍历完一个滑动窗口，就将以队头为下标的数(也就是每个滑动窗口的最大值)push到该数组，最后返回数组。

var nums = [1,3,-1,-3,5,3,6,7], k = 3;

var maxSlidingWindow = function(nums, k) {
    const len = nums.length;
    const res = [];
    const queue = [];//维护一个递减队列
    for (let i = 0; i < len; i++) {
        //打破递减趋势
        while (queue.length && nums[queue[queue.length-1]] <= nums[i]){
        queue.pop();
        }

        queue.push(i);

        //需要有值流出窗口
        while (queue.length && queue[0] <= i-k){
        queue.shift();
        }

        //该记录最大值
        if (i >= k-1){
        res.push(nums[queue[0]]);
        }
    }
    return res;
};

console.log(maxSlidingWindow(nums, k));

结语

快去试试滑动窗口的实例吧~