数据包优先级窗口查找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输出 32:3 后面第一个优先级更高的是 3:7输出 33:7 后面没有优先级更高的不输出该窗口输出: 3 3窗口 [1,3]: 数据包为 [2:3,3:7,4:6]2:3 后面第一个优先级更高的是 3:7输出 33: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输出 22:2 后面第一个优先级更高的是 3:3输出 33:3 后面没有优先级更高的不输出输出: 2 3窗口 [1,3]: 数据包为 [2:2,3:3,4:4]2:2 后面第一个优先级更高的是 3:3输出 33:3 后面第一个优先级更高的是 4:4输出 44: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