优先队列和单调队列有什么区别

P1886 滑动窗口 /【模板】单调队列

单调队列就是队列,只是通过pop来保持队列单调。 优先队列是STL,实质上是个堆,保持队列单调是通过排序而非“不满足单调性就扔掉”
by Kazeno_Akina @ 2023-11-25 12:52:52


@[_8008008](/user/803885) pq 带 log 但是单调队列不带 log
by Argvchs @ 2023-11-25 13:20:57


@[_8008008](/user/803885) 优先队列排序一次是nlogn,本题排(n-k+1)次,那么复杂度为O(nlogn(n-k+1)),显然不可行
by realheizi @ 2023-12-11 10:39:05


除非试一下离线算法,将数组排好序,通过条件一个个找找出当前的最大,或许可以实现O(nlogn+n)?
by realheizi @ 2023-12-11 10:41:04


|