2902 窗口最小和
大约 1 分钟
2902 窗口最小和
【算法】 滑动窗口
【C++】 滑动窗口、前缀和
【难度】 入门
一、题目简述
给定 个整数(可能包含负数),求所有长度为 的连续子数组的和的最小值。
数据范围:,。
二、解题思路
本题与 2901(窗口最大平均值)几乎是"对偶题",区别在于求最小值而非最大值。同样使用定长滑动窗口。
定长滑动窗口:维护当前窗口的元素和 sum。窗口右移时:
用 min 更新最小和即可。
由于元素可能为负数,窗口和也可能是负数,minSum 的初始值不能设为 0,应该设为第一个窗口的和。
手动模拟 [3, -1, 2, -4, 5, 1],k=3:
| 步骤 | 窗口范围 | 窗口元素 | 操作 | sum | minSum |
|---|---|---|---|---|---|
| 初始 | [1, 3] | 3, -1, 2 | 3+(-1)+2 | 4 | 4 |
| 右移 | [2, 4] | -1, 2, -4 | 4-3+(-4) | -3 | -3 |
| 右移 | [3, 5] | 2, -4, 5 | -3-(-1)+5 | 3 | -3 |
| 右移 | [4, 6] | -4, 5, 1 | 3-2+1 | 2 | -3 |
最小和 = -3。
三、参考代码
#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 minSum = sum;
// 滑动窗口
for (int i = k + 1; i <= n; i++) {
sum = sum - a[i - k] + a[i];
minSum = min(minSum, sum);
}
cout << minSum << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,遍历数组一次。
- 空间复杂度:,用于存储数组
a。
