大家好，我是吴师兄。
题目练习网址：https://www.algomooc.com/problem/X4029
视频讲解回放：https://www.algomooc.com/problem/X4029
“
下周二，全新的一期大厂算法训练营即将开营，每周定期讲解春招秋招真题，老学员可以继续免费参加，新同学可以添加微信 278166530 咨询
题目描述
小慕是一位工程师，他为主机配置了CPU监控告警系统。他想知道在一段时间内，主机上报了多少次告警。CPU监控数据以字符串数组
dataItems
的形式存储。
告警触发规则如下：如果在最近的时间段
interval
内，监控值连续
limit
次大于等于CPU使用率阈值
threshold
，则会触发告警。如果持续满足告警条件，可以多次上报告警。
请你帮助小慕计算该主机上报告警的总次数。
输入格式
输入分为五行：
第一行：监控数据的总个数
dataItemsLength
，整数，单位为个，例如
3
。
第二行：监控数据
dataItems
，字符串数组形式，其中
dataItems[i]
是第
i
条监控数据，包括当前CPU使用率值（取值范围
0
(
100
，整数）和当前时间戳（取值范围
0
)
2147483647
，整数，以升序排列）两部分内容，以英文逗号分隔，例如：
65,1705386526
。元素间以空格分隔，例如：
85,1705386526 80,1705386528 95,1705386530 90,1705386531 92,1705386532
。
第三行：告警统计时间段
interval
，整数，单位为秒，例如
4
，表示假定当前时间戳为
1705386532
，则统计从
1705386529
到
1705386532
时间范围内的数据，包含两端时间点的数据。
第四行：告警计算阈值
threshold
，整数，单位为百分比，例如
80
。
第五行：告警上报阈值
limit
，整数，单位为个，例如
2
。
输入范围说明：
1 ≤ dataItems.length ≤ 86400
1 ≤ interval ≤ 86400
1 ≤ threshold ≤ 100
1 ≤ limit ≤ 100
输出格式
返回该主机上报告警的次数。
样例
输入样例 1
1
85,1705386526
1
80
1
输出样例 1
1
提示 1
在最近1秒内，存在1条监控数据，连续超过CPU阈值80，满足告警触发条件，最终上报1条告警。
输入样例 2
5
85,1705386526 80,1705386528 95,1705386530 90,1705386531 92,1705386532
4
80
2
输出样例 2
4
提示 2
在最近4秒内，存在5条监控数据，连续超过CPU阈值80，其中4条监控数据（第2、3、4、5条）达到告警上报阈值2，满足告警触发条件，最终上报4条告警。
题目解析
以第二个用例为例：
故返回4个结果。
理解题目
本题要求计算主机在一段时间内上报的告警次数。告警的触发条件是：在一个给定的时间段
interval
内，CPU 使用率
CPU_usage
连续
limit
次超过阈值
threshold
，则会触发一次告警。如果在该时间段内持续满足条件，每次满足都会上报告警。
题目给定的输入包括：
-
-
监控数据
dataItems
，其中每个数据由
CPU_usage
和
timestamp
组成。
-
-
-
输出需要返回满足告警触发条件的总次数。
使用算法
本题的核心算法是滑动窗口（Sliding Window），结合双指针方法（Two Pointers）。
-
滑动窗口
：通过移动起始指针
i
和终止指针
j
，找到连续
limit
个满足
CPU_usage >= threshold
的子数组。
-
双指针
：遍历
dataItems
，当
CPU_usage
超过
threshold
时，利用
j
找到连续的超限区间，并通过
limit
和
interval
计算告警次数。
实现
代码实现思路如下：
-
-
-
解析
dataItems
，并拆分成
CPU_usage
和
timestamp
存入数组。
-
读取
interval
，
threshold
，
limit
。
-
-
使用
i
遍历数据，跳过
CPU_usage
小于
threshold
的数据。
-
通过
j
记录
CPU_usage >= threshold
的连续区间。
-
计算
limit
位置的时间戳，判断是否满足
interval
约束。
-
-
代码
Python
# https://www.algomooc.com/problem/X4029
n = int(input())
# 读取监控数据的总个数
info_str = input().split() # 读取监控数据，并按照空格分割为字符串列表
info = [list(map(int, s.split(','))) for s in info_str] # 将字符串转换为整数列表，存储 CPU 使用率和时间戳
interval = int(input()) # 读取告警统计时间段
threshold = int(input()) # 读取告警计算阈值
limit = int(input()) # 读取告警上报阈值
ans = 0# 初始化告警次数
i = 0# 初始化索引，遍历数据
while i < n:
# 如果当前 CPU 使用率小于阈值，直接跳过
if info[i][0] < threshold:
i += 1# 继续检查下一个数据
else:
j = i # 记录当前连续超限的起始索引
# 统计从 i 开始连续超过 threshold 的数据段
while j < n and info[j][0] >= threshold:
j += 1# 找到连续超限的终止位置
# 遍历找到的连续超限数据段，检查是否满足上报告警的条件
for k in range(i + limit - 1, j): # 从满足 limit 条件的起始位置开始遍历
# 检查 k 位置和 k-limit+1 位置的时间戳是否在 interval 内
if info[k][1] - info[k - limit + 1][1] + 1 <= interval:
ans += 1# 如果满足条件，告警次数加 1
i = j # 跳过已经处理的连续超限数据段
print(ans) # 输出告警次数
C++
// https://www.algomooc.com/problem/X4029
#include
#include
#include
usingnamespacestd;
int main() {
int n;
cin >> n; // 读取监控数据的总个数
cin.ignore(); // 清除换行符
vectorint, int>> info; // 存储CPU使用率和时间戳
string line, temp;
getline(cin, line); // 读取监控数据字符串
stringstream ss(line);
while (ss >> temp) {
size_t pos = temp.find(',');
int cpuUsage = stoi(temp.substr(0, pos));
int timestamp = stoi(temp.substr(pos + 1));
info.emplace_back(cpuUsage, timestamp);
}
int interval, threshold, limit;
cin >> interval >> threshold >> limit; // 读取告警统计时间段、计算阈值、上报阈值
int ans = 0;
int i = 0;
while (i < n) {
if (info[i].first < threshold) {
i++; // 若CPU使用率小于阈值，跳过
} else {
int j = i;
while (j < n && info[j].first >= threshold) {
j++; // 统计连续超过阈值的数据段
}
for (int k = i + limit - 1; k < j; k++) {
if (info[k].second - info[k - limit + 1].second + 1 <= interval) {
ans++; // 满足告警条件，增加告警次数
}
}
i = j; // 跳过已经处理的超限数据段
}
}
cout << ans <endl; // 输出告警次数
return0;
}
Java
import java.util.*;
publicclass Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取监控数据的总个数
scanner.nextLine(); // 清除换行符
List<int[]> info = new ArrayList<>(); // 存储CPU使用率和时间戳
String[] dataItems = scanner.nextLine().split(" "); // 读取监控数据字符串
for (String item : dataItems) {
String[] parts = item.split(",");
int cpuUsage = Integer.parseInt(parts[0]);
int timestamp = Integer.parseInt(parts[1]);
info.add(newint[]{cpuUsage, timestamp});
}
int interval = scanner.nextInt(); // 读取告警统计时间段
int threshold = scanner.nextInt(); // 读取告警计算阈值
int limit = scanner.nextInt(); // 读取告警上报阈值
int ans = 0;
int i = 0;
while (i < n) {
if (info.get(i)[0] < threshold) {
i++; // 若CPU使用率小于阈值，跳过
} else {
int j = i;
while (j < n && info.get(j)[0] >= threshold) {
j++; // 统计连续超过阈值的数据段
}
for (int k = i + limit - 1; k < j; k++) {
if (info.get(k)[1] - info.get(k - limit + 1)[1] + 1 <= interval) {
ans++; // 满足告警条件，增加告警次数
}
}
i = j; // 跳过已经处理的超限数据段
}
}
System.out.println(ans); // 输出告警次数
scanner.close();
}
}
时空复杂度
时间复杂度：
O(n)
。
空间复杂度：
O(n)
。
相关题目
485. 最大连续 1 的个数 - 力扣（LeetCode）
END
下周二，全新的一期大厂算法训练营即将开营，每周定期讲解春招秋招真题，老学员可以继续免费参加，新同学可以添加微信
278166530
咨询。
