满足以上两个条件的数据结构是单调递减双向队列,虽然名字长,但也很好理解的.
单调递减: {7,5,3,1},和我们之前讲过的单调栈是类似的.
双向队列:头尾两端都能进行压入和弹出操作....元素7,直接放入队列中,滑动窗口还没有真正形成,不用计算最大值
2. 滑动窗口右移,元素2加入队列中.取队列头7为最大值
3....滑动窗口右移,
要从队尾压入的元素为4,队尾元素2比要4小,弹出2,压入4;
左侧滑出滑动窗口范围的元素7,与队首元素相同,移除队列;
滑动窗口内最大值为4;
4....滑动窗口右移
要压入的元素5比队尾元素4大,弹出4,压入5;
队首元素为5,即滑动窗口中的最大值为5;
5. 滑动窗口右移
队尾压入元素1;
取队首元素5为滑动窗口最大值....综上,只要能维护好单调队列,就很容易取出滑动窗口的最大值.
而维护队列的过程只有两点:
1. 队尾压入元素时,要先将比该元素值小的元素从队尾弹出,最后再压入;
2.