一种简单但是神奇的数据结构,经常用来优化复杂度。

单调队列

意义

顾名思义,单调队列即具有单调性的队列。
队列头即为当前最大/最小的元素。
由于每个元素最多进队和出队一次,因此其复杂度为$O(n)$

实现

实现非常简单,只需要头尾两个指针即可,或者用STL封装好的deque

1
2
3
4
5
q[maxn];
int l,r,cur;
l = r = 0;
while(l < r && q[r-1]<cur) --r;
q[r++] = cur;

应用

  • poj2823
    单调队列+滑动窗口
    维护两个单调队列,每次区间的最小(大)值即为队首元素,若当前位置减去队首位置大于窗口大小,则弹出队首元素

DP的单调队列优化

  • hdu5289
    也是单调队列维护区间最大最小值,保证区间最大最小值差值小于k
    走到一个元素,加上其向左能延伸的最大长度,即其对其为最后一个元素,不同长度区间的贡献

  • poj1156
    上一题扩展到了二维。

  • hdu1506
    经典的广告印刷问题,两个方向扫描两次,维护单调队列求出当前高度向左(右)的最长延伸值

单调栈

和单调队列类似,即保持单调性的栈。
栈顶即为最大/最小元素。

应用没有单调队列广,直接用STL里的stack模拟即可

应用

  • poj3250
    从左向右扫描,维护一个递减的单调栈,每次加上栈顶以下的元素个数即可

  • Astar-2016-R2B A
    预处理每个值作为最小值最长区间