2026 华为OD机试真题 7月19日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

在工业物联网监控系统中，由于网络抖动、边缘节点缓存重发等原因，传感器上报数据往往是乱序到达；系统接收到一段数据流数据，流中的每个数据包包含一个发生时刻（单位秒）的时间戳和一个测量值；对于流中到达的每一个数据点，系统需要以该数据点的时间戳为基准，回溯过去一段时间内（包含当前时间戳），数据点的最大测量值是多少；请设计一段程序，按数据流 data 中各点的到达顺序，依次输出每个点对应回溯区间中的最大测量值。

2026 华为OD机试真题 7月19日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

数据流 data：二维数组格式，每个数组元素包括两个参数，发生时刻和该时刻的测量值；如 [1,10] 表示时刻 1 的测量值为 10；回溯时间 interval：整型格式，如当前时刻为 1，回溯时间为 5，那么表示回溯时间起点为 −4，回溯区间为 [−4,1]。

输出描述

每个时刻对应回溯区间的最大测量值组成的数组。

约束条件

• 1≤interval≤10^9
• 1≤data.length≤10^3
• −10^9≤value≤10^9

示例1

输入

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

输出

[10,12,10,12,10]

说明

1. 第 1 个到达 [1,10]：时间基准为 1，窗口为 [−3,1]。此时系统只有该点，最大值 =10。
2. 第 2 个到达 [6,12]：时间基准为 6，窗口为 [2,6]。系统已有 [1:10,6:12]，落在 [2,6] 内的只有 12，最大值 =12。
3. 第 3 个到达 [3,5]：时间基准为 3，窗口为 [−1,3]。系统已有 [1:10,6:12,3:5]，落在 [−1,3] 内的有 10 和 5（注意：时刻 6 在时刻 3 的未来，不属于过去 4 秒），最大值 =max(10,5)=10。
4. 第 4 个到达 [10,7]：时间基准为 10，窗口为 [6,10]。系统已有 [1:10,6:12,3:5,10:7]，落在 [6,10] 内的有 12 和 7，最大值 =12。
5. 第 5 个到达 [5,8]：时间基准为 5，窗口为 [1,5]。系统已有上述全部点，落在 [1,5] 内的有 10,5,8，最大值 =10。

示例2

输入

[[100,50],[95,80],[105,20]],10

输出

[50,80,80]

说明

1. 到达 [100,50]：窗口 [90,100]，最大值 50。
2. 到达 [95,80]：窗口 [85,95]，只有 80，最大值 80。
3. 到达 [105,20]：窗口 [95,105]，包含已到达的 (95:80,100:50,105:20)，最大值 80。

解题思路

核心思想

题目要求按数据到达顺序输出结果。对于第 i 个到达的数据点 [time, value]，只能在前 i + 1 个已经到达的数据点中查找，不能使用后续才到达的数据。

由于 data.length <= 1000，可以直接枚举每个当前点，再扫描所有已到达点，找出时间戳位于 [time - interval, time] 的最大测量值。

算法步骤

1. 按示例格式读取一行输入，解析出二维数组 data 和整数 interval。
2. 按到达顺序遍历 data[i] = [time, value]。
3. 当前回溯窗口为 [time - interval, time]。
4. 扫描下标 0..i 的已到达数据点。
5. 若某个已到达点的时间戳落在当前窗口内，则用它的测量值更新最大值。
6. 将当前最大值加入结果数组。
7. 最后按 [a,b,c] 格式输出结果。

复杂度分析

设数据点数量为 n。

• 每个点最多扫描此前所有点，时间复杂度为 O(n^2)。
• 结果数组占用 O(n)