双端队列deque 最后更新于 2025-05-02 08:28:45

```cpp #include<deque> using namespace std; deque<int> q;//双端队列 //q.push_front() 从前面加入 //q.pop_front() 从前面删除 //q.front() 询问前面的数是多少 //q.push_back() 从后面加入 //q.pop_back() 从后面删除 //q.back() 询问后面的数是多少 int a[maxn]; void push(int i)//单调队列的插入 插入下标为i的元素 要保证队列单调递增 { while (q.size() > 0 && a[q.back()] >= a[i]) q.pop_back(); q.push_back(i); } int main() { cin >> n; for (int i=1;i<=n;i++) cin >> a[i]; cin >> m;//所有长度为m的区间的最小值 for (int i=1;i<=n;i++) { push(i);//向单调队列里面加入a[i]这个元素 if (i-m == q.front()) q.pop_front();//把a[i-m]这个数删掉 if (i>=m)//区间长度已经超过m了 需要取出最小值 cout << a[q.front()] << "\n"; } } ```