给定一个数组和k大小的滑动窗口,找出所有滑动窗口里的最大值。...次大值会变成最大值;为了方便最大值的比较,最好是个有序的集合....对以上述的值集合还需要方便查询和删除最大值以及插入新值,并维护集合的有序性.
满足以上两个条件的数据结构是单调递减双向队列,虽然名字长,但也很好理解的....单调递减: {7,5,3,1},和我们之前讲过的单调栈是类似的.
双向队列:头尾两端都能进行压入和弹出操作.
查找过程:
1. 元素7,直接放入队列中,滑动窗口还没有真正形成,不用计算最大值
2....综上,只要能维护好单调队列,就很容易取出滑动窗口的最大值.
而维护队列的过程只有两点:
1. 队尾压入元素时,要先将比该元素值小的元素从队尾弹出,最后再压入;
2.