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

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

题目描述

给定 n 个数据包，每个数据包包含 id 和 priority。维护一个大小为 k 的滑动窗口，对于每个窗口，找出窗口内每个数据包右边第一个 priority 更高的数据包 id。

输入描述

• n: 数据包数量 (1≤n≤106)
• k: 窗口大小 (1≤k≤100)
• packets: 数据包内容，长度为 n 的数组，每个元素格式为 id:priority

数据包格式:

• 格式: \ :\
• id: 唯一标识符 (1≤id≤109)
• priority: 优先级 (1≤priority≤109)，数值越大优先级越高

处理规则:

• 窗口滑动: 从左到右滑动，每次窗口包含 k 个连续数据包

• 每个窗口的处理:

  • 向右查找第一个 priority 更高的数据包
  • 找到 → 记录该数据包的 id
  • 未找到 → 不记录

• 跳过条件: 数据包不足以构成完整窗口 (窗口大小 k> 数据包总数 n) → 跳过该窗口 窗口内未找到任何 priority 更高的数据包 → 跳过该窗口

输出描述

输出所有未跳过窗口的结果序列，每个序列包含该窗口内找到的所有"下一个更高优先级数据包 id"

示例1

输入

5,3,[[1,5],[2,3],[3,7],[4,6],[5,4]]

输出

[[3,3],[3]]

说明

窗口 [0,2]: 数据包为 [1:5,2:3,3:7]

1:5 后面第一个优先级更高的是 3:7，输出 3

2:3 后面第一个优先级更高的是 3:7，输出 3

3:7 后面没有优先级更高的，不输出

该窗口输出: 3 3

窗口 [1,3]: 数据包为 [2:3,3:7,4:6]

2:3 后面第一个优先级更高的是 3:7，输出 3

3:7 后面没有优先级更高的，不输出

4:6 后面没有优先级更高的，不输出

该窗口输出: 3

窗口 [2,4]: 数据包为 [3:7,4:6,5:4]

3:7 后面没有优先级更高的，不输出

4:6 后面没有优先级更高的，不输出

5:4 后面没有优先级更高的，不输出

该窗口无输出

示例2

输入

4,3,[[1,1],[2,2],[3,3],[4,4]]

输出

[[2,3],[3,4]]

说明

窗口 [0,2]: 数据包为 [1:1,2:2,3:3]

1:1 后面第一个优先级更高的是 2:2，输出 2

2:2 后面第一个优先级更高的是 3:3，输出 3

3:3 后面没有优先级更高的，不输出

输出: 2 3

窗口 [1,3]: 数据包为 [2:2,3:3,4:4]

2:2 后面第一个优先级更高的是 3:3，输出 3

3:3 后面第一个优先级更高的是 4:4，输出 4

4:4 后面没有优先级更高的，不输出

输出: 3 4

示例3

输入

4,3,[[4,4],[3,3],[2,2],[1,1]]

输出

[]

说明

窗口 [0,2]: 数据包为 [4:4,3:3,2:2]

4:4 后面没有优先级更高的，不输出

3:3 后面没有优先级更高的，不输出

2:2 后面没有优先级更高的，不输出

该窗口不输出

窗口 [1,3]: 数据包为 [3:3,2:2,1:1]

3:3 后面没有优先级更高的，不输出

2:2 后面没有优先级更高的，不输出

1:1 后面没有优先级更高的，不输出

该窗口不输出

所有窗口均无输出，最终结果输出 []

示例4

输入

3,4,[[1,5],[2,3],[3,7]]

输出

[]

说明

窗口大小 4> 数据包数量 3，窗口无输出，最终结果输出 []

解题思路

核心思想

本题要求在一个大小为 $k$ 的滑动窗口中，找出每个数据包右边（且在窗口内）的第一个优先级（priority）更高的数据包的 id。

1. 预处理“下一个更高优先级”：

   • 这是一个典型的 单调栈 (Monotonic Stack) 应用场景。
   • 我们可以利用单调递减栈，在 $O(n)$ 的时间内预处理出一个数组 next_greater，其中 next_greater[i] 存储的是数据包 $i$ 右侧第一个优先级更高的数据包的索引。如果右侧没有更高优先级的，则记为 -1。
   • 单调栈逻辑：遍历数据包时，如果当前数据包的优先级大于栈顶元素所对应数据包的优先级，说明当前数据包就是栈顶元素右侧第一个更大的元素。将栈顶弹出并记录，直到栈为空或栈顶优先级大于等于当前优先级，然后将当前元素的索引入栈。

2. 滑动窗口扫描：

   • 窗口大小为 $k$。如果 $k > n$ 或 $k \le 0$，说明无法形成完整的窗口，直接返回空结果。
   • 共有 $n - k + 1$ 个窗口。对于每一个起点 start，窗口的范围是 [start, end]（其中 end = start + k - 1）。
   • 遍历当前窗口内的每一个位置 i，检查它预处理好的 next_greater[i]。
   • 有效性判断：如果 next_greater[i] 存在（即不为 -1），且这个“下一个更大”的位置 仍然在当前窗口范围内（即 next_greater[i] <= end），那么我们就找到了符合条件的数据包，将其 id 加入当前窗口的结果列表。
   • 如果一个窗口内找到了至少一个符合条件的 id，则将该窗口的结果集保存。否则，跳过该窗口。

复杂度分析

• 时间复杂度：
  • 单调栈预处理 next_greater：每个元素最多入栈一次，出栈一次，时间复杂度为 $O(n)$。
  • 滑动窗口遍历：共有 $n - k + 1$ 个窗口，每个窗口遍历 $k$ 个元素，总耗时约为 $O((n - k) \times k) \approx O(n \cdot k)$。
  • 总体时间复杂度为 $O(n \cdot k)$。鉴于 $k \le 100$，$n \le 10^6$，最大操作次数约为 $10^8$，在常规机试时间限制内可以高效通过。
• 空间复杂度：
  • 需要存储 ids 和 priorities 数组，大小为 $O(n)$。
  • 需要单调栈 stack 和结果数组 next_greater，大小为 $O(n)$。
  • 总体空间复杂度为 $O(n)$。