Skip to content

Latest commit

 

History

History
14 lines (8 loc) · 969 Bytes

monotonous-queue.md

File metadata and controls

14 lines (8 loc) · 969 Bytes

单调队列

代码

用来求滑动窗口最大值/最小值。以求最大值为例:

思路:如果一个数 a 在数 b 左边,且 a <= b,那么如果 b 在滑动窗口内,a 就一定不可能是滑动窗口最大值。

维护一个队列,队头到队尾对应的值严格单减。每次拿队尾元素比较,不断 pop_back 直到队尾元素大于当前元素。然后把队头的不在窗口内的值去掉,此时队头就是最大值。

队列中可以存下标,也可以存值,如果存值的话需要记录一下队列实际的大小,以及每个队列元素对应多少个不在队列中的元素。因为插入每个元素前,我们 pop_back 了一部分元素,这部分元素实际上还在窗口中,所以需要记录下来。而 pop_front 时,需要看在滑动窗口中,单调队列的队头元素的前面有没有元素。

  • 时间复杂度:O(n)
  • 空间复杂度:O(k)