2901 窗口最大平均值
大约 2 分钟
2901 窗口最大平均值
【算法】 滑动窗口
【C++】 滑动窗口、前缀和、printf格式化
【难度】 入门
一、题目简述
给定 个整数 ,求所有长度为 的连续子数组的平均值的最大值,结果保留两位小数。
数据范围:,。
二、解题思路
暴力做法:枚举每个起点 ,计算 到 的和,取最大值。复杂度 ,当 接近 时会超时。
定长滑动窗口优化:长度为 的窗口每次右移一位,左边出一个元素,右边进一个元素。可以利用前一个窗口的和快速计算当前窗口的和,避免重复累加。
设当前窗口和为 sum,窗口右移时:
其中 是新进入窗口的元素, 是离开窗口的元素。
算法步骤:
- 先计算第一个窗口(下标 到 )的和,记为
sum和maxSum - 从 遍历到 ,每次更新
sum = sum - a[i-k] + a[i],用max维护最大和 - 最终最大平均值 =
maxSum / k,用printf("%.2f")保留两位小数输出
为什么用 long long?最坏情况 ,和最大约 ,在 int 范围内(约 ),但为了安全和习惯,使用 long long。
手动模拟 [1, 2, 3, 4, 5],k=3:
| 步骤 | 窗口范围 | 操作 | sum | maxSum |
|---|---|---|---|---|
| 初始 | [1, 3] | 1+2+3 | 6 | 6 |
| 右移 | [2, 4] | 6-1+4 | 9 | 9 |
| 右移 | [3, 5] | 9-2+5 | 12 | 12 |
最大和 = 12,最大平均值 = 12 / 3 = 4.00。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
// 第一个窗口的和
long long sum = 0;
for (int i = 1; i <= k; i++) sum += a[i];
long long maxSum = sum;
// 滑动窗口
for (int i = k + 1; i <= n; i++) {
sum = sum - a[i - k] + a[i];
maxSum = max(maxSum, sum);
}
printf("%.2f\n", (double)maxSum / k);
return 0;
}四、复杂度分析
- 时间复杂度:,每个元素恰好进入窗口一次、离开窗口一次,共 次操作。
- 空间复杂度:,存储数组
a。虽然滑动窗口本身只需 额外空间,但原始数组需要 存储。
