[数据结构与算法]NC82 滑动窗口的最大值

NC82 滑动窗口的最大值

刚开始看到这题我也只有暴力的想法，O(n*k)

然后去看了官方的题解

• 当num数组长度小于size和size等于0时 直接返回 []

• queue为一个可以两端进行删除，并在末尾插入的队列

• 遍历num数组，维护queue为递减队列

• 当queue为空时，直接入队

• 当num[i]大于queue的队尾元素时，队尾元素pop，知道队尾元素大于num[i]或者队空。然后让num[i]入队

• 当num[i]小于queue队尾元素时，元素直接入队

• 当队头元素下标不属于当前窗口，直接出队

• 当i > size + 1时，也就是当前有效窗口下，队头元素就是当前窗口的最大值，队头元素出队，然后push

• 进ans数组即可

• 最后将ans数组返回

  function maxInWindows(num, size)
  {
      if(num.length < size || size == 0) return []
  //     用来存放当前窗口递减的数值下标
      let queue = []
  //     存放返回的结果
      let ans = []
      for(let i = 0 ; i < num.length ; i++){
          if(queue.length == 0){
              queue.push(i)
          }else if(num[queue[queue.length - 1]] <= num[i]){
              while(num[queue[queue.length - 1]] <= num[i]){
                  queue.pop()
              }
              queue.push(i)
          }else{
              queue.push(i)
          }
  //         当队列的头下标已经不在当前窗口 则去掉
          if(queue.length != 0 && (i - queue[0] >= size)){
              queue.shift()
          }
          if(i >= size - 1){
              ans.push(num[queue[0]])
          }
          
      }
      return ans
  }
  module.exports = {
      maxInWindows : maxInWindows
  };