Skip to content

Latest commit

 

History

History
5 lines (3 loc) · 398 Bytes

monotonic_queue.md

File metadata and controls

5 lines (3 loc) · 398 Bytes

Monotonic Queue (单调队列)

非常巧妙地一种思想,使用deque维护一个单调递增或递减的队列,同时记录每个元素的位置,这样就可以保证区间长度k的前提下求解最大、最小值。 由于每个元素只进队出队一次,且deque的入队出队操作时间复杂度均为O(1),所以整体时间复杂度为O(n),非常优秀,非常优美!