【题目描述】
给定一个序列,使用 deque 维护一个大小为 k 的窗口,计算每个窗口中所有元素的平均值。
【算法分析】
● STL deque:https://cplusplus.com/reference/deque/
● 在 C++ 标准模板库(STL)中,deque(double-ended queue,双端队列)是一个非常重要的容器,它支持在序列的两端进行快速插入和删除操作。所以,对于需要在两端进行修改的数据结构,例如滑动窗口,deque是一个理想的选择。
● 本例使用 STL deque 的 push_back() 函数创建 deque:https://cplusplus.com/reference/deque/deque/push_back/
【算法代码】
#include <bits/stdc++.h>
using namespace std;void sliding_window_avg(deque<int> deq, int k) {double sum=0;for(int i=0; i<deq.size(); i++) {sum+=deq[i];if(i>=k) sum-=deq[i-k];if(i>=k-1) {cout<<"Average of "<<k<<" elements: "<<sum/k<<endl;}}
}int main() {deque<int> deq;int n,x,k;cin>>n;while(n--) {cin>>x;deq.push_back(x);}cin>>k;sliding_window_avg(deq,k);return 0;
}/*
in:
9
2 8 1 6 3 5 7 4 9
5out:
Average of 5 elements: 4
Average of 5 elements: 4.6
Average of 5 elements: 4.4
Average of 5 elements: 5
Average of 5 elements: 5.6
*/
【参考文献】
https://cplusplus.com/reference/deque/deque/push_back/
https://mp.weixin.qq.com/s/hNb_V3ffphCr_8Z30NPryQ