• 我们都知道，若是一个数字A进入窗口后，若是比窗口内其他数字都大，那么这个数字之前的数字都没用了，因为它们必定会比A早离开窗口，在A离开之前都争不过A，所以A在进入时依次从尾部排除掉之前的小值再进入，每次有新值进入的时候，都会判断是不是比当前的值小，所以每次其实都比较判断了一次。如果新值比当前值（窗口内）小，那么不能确定新值以后是否还有用，所以保留。


其核心就是，获得了第一个最大值之后。（仅有一个最大值）。然后开始往后滑动窗口，每次滑动一个值，即每次都往队列添加一个值，但是每次在添加之前，拿新进入的值和队列里的所有值进行比较（即去掉比自己先进队列的小于自己的值），因为新值若大，之前的值肯定全没有代表性了。即争不过新值。下次在比较的时候，就可以少比较一点，因为去除了那些刚刚去除的小值，所以比暴力法逐个窗口计算要快
  • 而每次窗口移动要弹出窗口最前面值，因此队首也需要弹出，所以我们选择双向队列。
    while(!dq.empty() && dq.front() < (i - size + 1))
                        //弹出窗口移走后的值
                        dq.pop_front(); 

  • step 1：维护一个双向队列，用来存储数列的下标。
  • step 2：首先检查窗口大小与数组大小。
  • step 3：先遍历第一个窗口，如果即将进入队列的下标的值大于队列后方的值，依次将小于的值拿出来去掉，再加入，保证队列是递增序。
1
2
3
4
5
6
7
//先遍历一个窗口
for(inti = 0; i < size; i++){
    //去掉比自己先进队列的小于自己的值
   
 while(!dq.empty() && num[dq.back()] < num[i])
                    dq.pop_back();
                dq.push_back(i);
}
  • step 4：遍历后续窗口，每次取出队首就是最大值，如果某个下标已经过了窗口，则从队列前方将其弹出。
  •                              while(!dq.empty() && dq.front() < (i - size + 1))
  • (i - size + 1)//当前窗口左边界，dq.front() 上一个窗口最大值的下标，说明最大值已经失效，出队列

  • step 5：对于之后的窗口，重复step 3，直到数组结束
  •     //去掉比自己先进队列的小于自己的值，
  •   while(!dq.empty() && num[dq.back()] < num[i])
                        dq.pop_back();
                    dq.push_back(i);