解题思路

先把每个数据包拆成两个数组：

• ids[i] 表示第 i 个数据包的 id
• priorities[i] 表示第 i 个数据包的 priority

题目要求：对于每个长度为 $k$ 的滑动窗口，找到窗口内每个数据包右边第一个 priority 更高的数据包，并输出那个数据包的 id。如果一个窗口里没有任何位置满足条件，则跳过该窗口。

题目内容

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

输入描述

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

数据包格式:

• 格式: $<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$

样例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$，窗口无输出，最终结果输出 $[]$