20260729-基于上报数据的实时最大值（N0055）- 算法机考高频题型 · 华为OD / 100分题解 | AlgoMooc

N0055. 20260729-基于上报数据的实时最大值

简单

通过率 100% · 提交 6 · 通过 6

100分华为OD模拟

算法机考高频题型改编 · 聚焦「100分 / 华为OD」 · 难度：简单

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

这类题属于算法机考高频题型中「100分 / 华为OD」方向的高频题型，通常考察对「100分 / 华为OD」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

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

输出描述

每个时刻对应回溯区间的最大测量值组成的数组；约束条件：

1 ≤ interval ≤ 10^9
1 ≤ data.length ≤ 10^3
-10^3 ≤ value ≤ 10^9

示例

示例 1

输入示例

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

输出示例

10,12,10,12,10

说明：

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

示例 2

输入示例

3
100,50 95,80 105,20
10

输出示例

50,80,80

说明：

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

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param data 二维数组，每个元素为 [time, value]，表示数据流中的数据点
# @param interval 回溯时间间隔
# @return 每个时刻对应回溯区间的最大测量值组成的数组
class Solution:
    def getMaxValues(self, data: List[List[int]], interval: int) -> List[int]:
        pass


# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写
if __name__ == "__main__":
    n = int(input().strip())
    line = input().strip()
    interval = int(input().strip())
    data = []
    if line:
        for part in line.split():
            t, v = part.split(",")
            data.append([int(t), int(v)])
    sol = Solution()
    ans = sol.getMaxValues(data, interval)
    print(",".join(map(str, ans)))

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交