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;
};
上一篇:239. 滑动窗口最大值


下一篇:239. 滑动窗口最大值