Leetconde(239)：利用双向队列解滑动窗口问题

题目描述

解题思路

维护以下2个动态数组
1、双向队列temp
它用于保存原数组的下标，队首是当前窗口中的最大值
利用pop方法实现队尾出队，利用splice(0,1)实现队首出队
2、普通数组arr
在每一轮循环最后，将temp的队首推入arr
循环结束后，返回arr

其实我们可以弱化“窗口”这个概念，因为对于队列temp来说，它的长度是不固定的

为了简化表述，将会用队列代指temp

在每一轮循环中（i从0走到nums.length-1）

• 若队首已不在窗口中，则队首出队
• 将当前元素nums[i]依次与队列尾部元素进行比较：若nums[i]较大，则当前队尾应该出队（因为它不可能在将来成为队首）;直到nums[i]较小 or 队列已空
• 当前元素nums[i]入队
• 从第K次循环开始(i>=k-1)，将队首放入数组arr中

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    var temp=new Array()
    var arr=new Array()

    //var finished=nums.length-k
    for(let i=0;i<nums.length;i++){
        if(i==0){
            temp.push(i)
        }else{

            if(Math.abs(i-temp[0])>=k){
                temp.splice(0,1)
            }

            while(true){
                if(temp.length===0){
                    break
                }

                let j=temp[temp.length-1]//temp队尾
                if(nums[j]<nums[i]){
                    temp.pop()
                }else{
                    break
                }
            }

            temp.push(i)

        }

        if(i>=k-1){
            arr.push(nums[temp[0]])
        }
    }

    return arr;
};