目录

题目

思路

Code

题目

题目内容：

工业物联网监控系统中，传感器上报数据可能因为网络抖动或边缘节点缓存重发而乱序到达。系统接收到一段数据流，每个数据点包含发生时刻和测量值。

对于数据流中到达的每一个数据点，需要以该数据点的时间戳为基准，回溯过去一段时间内，包含当前时间戳，已到达数据点中的最大测量值。

请按数据流 data 中各点的到达顺序，依次输出每个点对应回溯区间中的最大测量值。

约束：1 <= interval <= 10^9；1 <= data.length <= 1000；-1000 <= value <= 10^9。

输入描述：

第一行输入数据流 data，每个数据点格式为 time,value，多个数据点之间用空格分隔。

第二行输入整数 interval，表示回溯时间长度。

输出描述：

输出每个数据点对应回溯区间的最大测量值，多个结果用英文逗号分隔。

样例 1

输入：

1,10 6,12 3,5 10,7 5,8
4

输出：

10,12,10,12,10

说明：

第三个数据点时间戳为 3，窗口为 -1 到 3，只考虑已经到达且时间落入窗口的数据点，因此最大值为 10。

样例 2

输入：

100,50 95,80 105,20
10

输出：

50,80,80

说明：

第三个数据点窗口为 95 到 105，已到达数据点中时间 95、100、105 都在窗口内，最大值为 80。

思路

整体思路：数据量最多 1000，可以直接按到达顺序做二重枚举。

第一步：处理第 i 个数据点时，根据它的时间戳 t 得到窗口下界 t - interval 和上界 t。

第二步：只枚举已经到达的数据点，也就是下标不超过 i 的数据点，判断时间戳是否落在当前窗口内。

第三步：对窗口内的数据点持续更新最大测量值，得到当前数据点对应的输出。

边界处理：窗口包含左右端点，且数据可能乱序到达，所以不能按时间排序后滑动窗口。

复杂度分析：共有 n 个数据点，每次最多检查 n 个已到达数据点，时间复杂度 O(n^2)，额外空间 O(n)。

Code

import sys


def solve(data, interval):
    ans = []
    for i, (t, value) in enumerate(data):
        # 窗口是围绕当前数据点的发生时刻定义的，乱序到达时不能沿用上一条数据的窗口。
        left = t - interval
        best = value
        # 题目强调“已到达数据点”，所以这里只枚举下标不超过 i 的前缀。
        for old_t, old_value in data[:i + 1]:
            # 时间戳落在 [t-interval, t] 的点才参与当前最大值计算，边界点也有效。
            if left <= old_t <= t and old_value > best:
                best = old_value
        # 输出顺序不是按时间戳排序，而是和数据流到达顺序保持一致。
        ans.append(best)
    return ans

line = sys.stdin.readline().strip()
interval = int(sys.stdin.readline().strip())
data = []
if line:
    for part in line.split():
        # 空格分隔的是到达事件，逗号内部才是一个事件的 time 和 value。
        t, v = map(int, part.split(","))
        data.append((t, v))
print(",".join(map(str, solve(data, interval))))

JS

const fs = require("fs");
const lines = fs.readFileSync(0, "utf8").trim().split(/\n/);
const parts = lines[0].trim() ? lines[0].trim().split(/\s+/) : [];
const interval = Number(lines[1].trim());
// parts 的顺序就是上报到达顺序，不能按 time 字段重排。
const data = parts.map(p => p.split(",").map(Number));
const ans = [];
for (let i = 0; i < data.length; i++) {
  const [t, value] = data[i];
  // 当前事件自己的时间戳决定窗口右端点，乱序输入会让窗口范围前后跳动。
  const left = t - interval;
  let best = value;
  for (let j = 0; j <= i; j++) {
    const [oldT, oldValue] = data[j];
    // j <= i 保证数据已经到达；oldT 落在闭区间内才参与最大值计算。
    if (oldT >= left && oldT <= t && oldValue > best) best = oldValue;
  }
  // 每处理一个到达事件就生成一个答案，输出顺序自然跟随数据流。
  ans.push(best);
}
console.log(ans.join(","));

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。