以求滑动窗口内最小值为例:
有 2 3 1 4 7 8 5 一组数据,有一个范围为 3 的的滑动窗口,每次向右移动 1 距离,求每次滑动的最小值
队列特性
- 维护一个最大为 3 个数的队列,且该队列具有单调性(队列内的数据呈现单调递增或递减)
- 元素进队只能从队尾进,队头,队尾都可出
- 从尾进队:是必进队;新元素进队前会先循环判断是否比队尾元素更有优势(这个列子里就是更小),如果更优,会将队尾元素出队,再次循环直至队列为空或者不是更优,再进队
- 从头出队条件:窗口滑动了,头元素下标超过尾元素下标差值大等于了窗口范围(head+3<=tail)
- 从尾出队条件:新元素比尾更有优势
过程:
第一个元素进入 2
[2] ---进之前队列为空,直接进入
第二个元素进入 3
[2,3] ---队列不为空,且不是更优,头下标没有超出范围,直接进入
第三个元素进入 1
[2,3] 1->[2] 1->[1] ---循环判断到队列为空,再进入
第四个元素进入 4
[1,4]
第五个元素进入 7
[1,4,7]
第六个元素进入 8
[1,4,7]->[4,7,8] ---头洗标超出范围,头元素出队,再进队
第七个元素进入 5
[4,5] ---循环判断至不是更优,再进入