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

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

题目描述

在数据包传输系统中，为了优化网络带宽利用率，系统需要对数据包序列进行处理，找出每个数据包右侧第一个满足某些条件、优先级更高的数据包。

每个数据包的格式为：`

:`，其中： * ` ` 是数据包的优先级（正整数，`1 ≤ priority ≤ 10^5`，数值越大优先级越高） * ` ` 是数据包的权重（正整数，`1 ≤ weight ≤ 10^5`） 系统需要按照以下规则处理数据包：搜索整个数据包序列（从左到右），对于每个数据包，找出其右侧第一个同时满足如下条件的数据包： * 条件1：目标数据包的 `priority` 必须大于当前数据包的 `priority` * 条件2：目标数据包的 `weight` 必须等于当前数据包的 `weight` 请编写一个方法，实现数据包右侧第一个满足条件的数据包查找功能。 > 2026 华为OD机试真题 7月12日华为OD上机新系统考试真题 100 分题型 # 输入描述 参数 packets：数据包内容，长度为 n（正整数，`1 ≤ n ≤ 10^5`）的数组，每个元素为 `[priority, weight]`。 # 输出描述 右侧第一个满足条件的数据包 ID 组成的数组序列；数据包 ID 是其在数组中的位置，即第 i 个数据包的 ID 为（从 1 开始计数，非数组下标 0）；如果某个数据包右侧没有满足条件的数据包，则输出 0。 # 示例1 输入 ``` [[5,10],[6,10],[4,10]] ``` 输出 ``` [2,0,0] ``` 说明 > 数据包序列：`[[5,10],[6,10],[4,10]]` > > * 第 1 个数据包 `[5,10]` 右侧搜索： > * 第 2 个 `[6,10]`：`priority(6) > 5`，`weight(10)` 相同，满足条件，输出 2（非数组下标 1） > > * 第 2 个数据包 `[6,10]` 右侧搜索： > > * 第 3 个 `[4,10]`：`priority(4) * 没有满足条件的，输出 0 > > * 第 3 个数据包 `[4,10]` 右侧搜索： > * 右侧没有数据包，没有满足条件的，输出 0 > > * 最终输出：`[2,0,0]` # 示例2 输入 ``` [[5,10],[7,22]] ``` 输出 ``` [0,0] ``` 说明 > 数据包序列：`[[5,10],[7,22]]` > > * 第 1 个数据包 `[5,10]` 右侧搜索： > > * 第 2 个 `[7,22]`：`priority(7) > 5`，`weight(22) ≠ 10`，不满足 > * 没有满足条件的，输出 0 > > * 第 2 个数据包 `[7,22]` 右侧搜索： > * 右侧没有数据包，没有满足条件的，输出 0 > > * 最终输出：`[0,0]` # 解题思路 ## 核心思想 本题是经典的 **"下一个更大元素"** 问题的变体。由于约束条件是**同 weight** 且**右侧第一个 priority 严格更大**，我们可以： 1. 按 `weight` 分组，因为只有相同 weight 的数据包之间才需要相互匹配。 2. 在每个 weight 组内从右向左扫描，使用**单调栈**维护 priority 严格递增的数据包下标。 ## 算法步骤 1. **分组**：使用 `defaultdict(list)` 按 `weight` 将数据包分组，记录每个数据包的 `(原始下标, priority)`。 2. **逐组处理**：对每个 weight 组，从右向左遍历，使用单调栈 `stack` 存储候选下标。 3. **维护单调栈**：对于当前 `(idx, pr)`： - 弹出栈中所有 `priority