当前位置：首页 > article >正文

滑动窗口元素的平均值 ← STL : deque

article 2024/9/20 13:47:38

【题目描述】
给定一个序列，使用 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
5

out:
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

查看全文

http://www.kler.cn/news/285123.html