双端队列
入门双端队列把"从哪边进、从哪边出"都交给算法自己决定。
// 算法讲解
双端队列
会同时演示头插、尾插和双端弹出。
待机
速度 中
待机 ⌨1deque<int> dq;
2
3void pushBothEnds(int leftValue, int rightValue) {
4 dq.push_front(leftValue);
5 dq.push_back(rightValue);
6}
7
8void trim() {
9 if (!dq.empty()) dq.pop_front();
10 if (!dq.empty()) dq.pop_back();
11}
复杂度分析
时间 两端操作 O(1)
空间 O(n)
最优 O(1)
最坏 O(1)
算法讲解
双端队列允许在头尾两侧都进行插入和删除，因此比普通队列更灵活。
它在滑动窗口最值、0-1 BFS、回文检查等问题中经常出现。
学习时要明确具体算法为什么要从左边弹还是从右边压，这通常对应状态的淘汰策略。
如果再叠加"保持单调"的规则，就能得到竞赛里非常常见的单调队列技巧。