统计业务流量的毫秒级峰值 - 华为机试真题题解

考试平台：时习知

分值： 200分（第二题）

考试时间：两小时（共3题）

alt

题目描述

业务模块往外发送报文时，有时会出现网卡队列满而丢包问题，但从常规的秒级流量统计结果看，业务的流量并不大。

实际上可能是业务出现了毫秒级的流量突出，导致短时间内超过出了网卡的处理能力;而这种突发持续时间并不长，因此，秒级统计结果呈现不出异常。

现给出一段时间内各个时间点业务发送的报文数，请统计出此段时间内流量的毫秒级峰值，即1毫内业务发送的最大报文数 (时间戳相差小于1毫秒范围的发送报文数，不含时间戳相差正好为1毫秒的时刻)

输入

第1行:n，标示这段时间内有多少条记录 (即后续还有n行数据)，n的取值范围为[1,1000000]

第2行开始，每行的数据格式为:t m，标示为某个时间点t(随着行数的增加，t会随之变大)，业务发送的报文数m，

其中，t的单位为微秒，取值范围为[1,268435455]，1毫秒等于1000微秒;

m的取值范围为[1，1000]

输出

m，表示这段时间内流量的毫秒级峰值，即1毫秒内业务发送的最大报文数(时间戳相差小于1毫秒范围的发送报文数，不含时间戳相差正好为1毫秒的时刻)

示例1

输入：
3
1024 100
1050 100
2100 150

输出：
200

解释： 
前两条记录在一个毫秒内，报文数为200，第2条和第3条记录不属于同个毫秒内

示例2

输入：
3
1024 100
1050 100
2100 250

输出：
250

解释： 
第3条记录和前面的记录不在一个时间点内，而它的值最大

Python 题解

统计一段时间内毫秒级流量峰值的程序。以下是代码的一些解释：

from collections import deque 引入双端队列（deque）来维护时刻和报文数的记录。
n = int(input()) 获取输入，表示有多少条记录。
初始化 max_ans 为最大结果值，sum 为队列中的总报文数，q 为双端队列。
使用循环遍历每一条记录，获取时刻 t 和报文数 m。
将时刻和报文数添加到队列中，并更新总报文数 sum。
使用 while 循环，判断最早的报文是否和当前时刻相差大于等于1毫秒，如果是，则从队列中移除，并更新总报文数 sum。
在每次循环内都尝试更新最大值 max_ans，保留当前时刻1毫秒内的报文总数的最大值。
循环结束后，输出最终的结果 max_ans。

这个程序通过使用双端队列来维护1毫秒内的报文数，实时更新最大值。通过循环遍历所有记录，可以得到最终的结果。

Python 题解

from collections import deque

n = int(input())

# 最大的结果值， 队列中的总报文数
max_ans, sum = 0, 0
q = deque()

for _ in range(n):
    # 时刻t, 报文数m
    t, m = map(int, input().split())
    q.append((t, m))
    sum += m

    # 最早的报文和当前时间不在 1 毫秒内，因此抛弃
    while q and t - q[0][0] >= 1000:
        sum -= q.popleft()[1]

    # 尝试更新最大值
    max_ans = max(max_ans, sum)


print(max_ans)