)
数据包优先级窗口查找
2026 华为OD机试真题 5月13日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
给定 n 个数据包，每个数据包包含 id 和 priority。维护一个大小为 k 的滑动窗口，对于每个窗口，找出窗口内每个数据包右边第一个 priority 更高的数据包 id。
2026 华为OD机试真题 5月13日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
输入描述
- 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。
预处理“下一个更高优先级”： - 这是一个典型的单调栈 (Monotonic Stack)应用场景。 - 我们可以利用单调递减栈，在 $O(n)$ 的时间内预处理出一个数组
next_greater，其中next_greater[i]存储的是数据包 $i$ 右侧第一个优先级更高的数据包的索引。如果右侧没有更高优先级的，则记为-1。 -单调栈逻辑：遍历数据包时，如果当前数据包的优先级大于栈顶元素所对应数据包的优先级，说明当前数据包就是栈顶元素右侧第一个更大的元素。将栈顶弹出并记录，直到栈为空或栈顶优先级大于等于当前优先级，然后将当前元素的索引入栈。滑动窗口扫描： - 窗口大小为 $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
