次大值会变成最大值;为了方便最大值的比较,最好是个有序的集合....对以上述的值集合还需要方便查询和删除最大值以及插入新值,并维护集合的有序性.
满足以上两个条件的数据结构是单调递减双向队列,虽然名字长,但也很好理解的....元素7,直接放入队列中,滑动窗口还没有真正形成,不用计算最大值
2. 滑动窗口右移,元素2加入队列中.取队列头7为最大值
3....滑动窗口右移
要压入的元素5比队尾元素4大,弹出4,压入5;
队首元素为5,即滑动窗口中的最大值为5;
5. 滑动窗口右移
队尾压入元素1;
取队首元素5为滑动窗口最大值....单调队列适合解决在一定范围内保存最大值(或者最小值),次大值(次小值)等等.