数据包优先级窗口查找（N0022）- 算法机考高频题型 · 100分 / 滑动窗口题解 | AlgoMooc

N0022. 20260513-数据包优先级窗口查找

困难

社区常称：数据包优先级窗口查找

通过率 30% · 提交 67 · 通过 20

100分滑动窗口单调栈队列

概念速查：单调栈是什么

算法机考高频题型改编 · 聚焦「100分 / 滑动窗口」 · 难度：困难

小慕正在处理一批数据包，共有 n 个，每个数据包有一个 id 和一个 priority 值。现在，小慕需要维护一个大小为 k 的，对于窗口内的每个数据包，找出它的 id。

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

提示：带虚线的词点一下有通俗解释。

输入描述

n ：数据包数量（1≤n≤10^6）
k ：窗口大小（1≤k≤100）
packets ：数据包内容，长度为 n 的数组，每个元素格式为 id:priority 数据包格式：
格式：:
id ：唯一标识符（1≤id≤10^9 ）
priority ：优先级（1≤priority≤10^9 ），数值越大优先级越高处理规则：
窗口滑动：从左到右滑动，每次窗口包含 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

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

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

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

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

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param n int整型 数据包数量
# @param k int整型 窗口大小
# @param packets string字符串一维数组 每个元素格式为 "id:priority"
# @return string字符串一维数组 每个窗口的结果序列

class Solution:
    def findNextHigher(self, n: int, k: int, packets: List[str]) -> List[str]:
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写

n = int(input())
k = int(input())
packets = input().split()
sol = Solution()
result = sol.findNextHigher(n, k, packets)
print(*result)

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

输入描述

输出描述

示例

我的提交