企业官网建设流程全解析

数据包优先级窗口查找

华为OD新系统机试真题 华为OD新系统上机考试真题 5月13号 100分题型

更多语言题解可点击查看：华为OD机试新系统真题 - 数据包优先级窗口查找(C/C++/Py/Java/Js/Go)题解

华为OD机试新系统真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解

题目内容

给定n nn个数据包，每个数据包包含i d idid和p r i o r i t y prioritypriority。维护一个大小为k kk的滑动窗口，对于每个窗口，找出窗口内每个数据包右边第一个p r i o r i t y prioritypriority更高的数据包i d idid。

输入描述

• n nn: 数据包数量 (1 ≤ n ≤ 10 6 1 ≤ n ≤ 10^61≤n≤106)
• k kk: 窗口大小 (1 ≤ k ≤ 100 1 ≤ k ≤ 1001≤k≤100)
• p a c k e t s packetspackets: 数据包内容，长度为n nn的数组，每个元素格式为i d : p r i o r i t y id:priorityid:priority
  数据包格式:
• 格式:< i d > : < p r i o r i t y > <id>:<priority><id>:<priority>
• i d idid: 唯一标识符 (1 ≤ i d ≤ 10 9 1 ≤ id ≤ 10^91≤id≤109)
• p r i o r i t y prioritypriority: 优先级 (1 ≤ p r i o r i t y ≤ 10 9 1 ≤ priority ≤ 10^91≤priority≤109)，数值越大优先级越高
  处理规则:
• 窗口滑动: 从左到右滑动，每次窗口包含k kk个连续数据包
• 每个窗口的处理:
• 向右查找第一个p r i o r i t y prioritypriority更高的数据包
• 找到 → 记录该数据包的i d idid
• 未找到 → 不记录
• 跳过条件: 数据包不足以构成完整窗口 (窗口大小k > k >k>数据包总数n nn)→ →→跳过该窗口 窗口内未找到任何p r i o r i t y prioritypriority更高的数据包→ →→跳过该窗口

输出描述

输出所有未跳过窗口的结果序列，每个序列包含该窗口内找到的所有"下一个更高优先级数据包i d idid"

样例1

输入

5 3 1:5 2:3 3:7 4:6 5:4

输出

3,3 3

说明

窗口[ 0 , 2 ] [0,2][0,2]: 数据包为[ 1 : 5 , 2 : 3 , 3 : 7 ] [1:5, 2:3, 3:7][1:5,2:3,3:7]
1 : 5 1:51:5后面第一个优先级更高的是3 : 7 3:73:7，输出3 33
2 : 3 2:32:3后面第一个优先级更高的是3 : 7 3:73:7，输出3 33
3 : 7 3:73:7后面没有优先级更高的，不输出
该窗口输出:3 333 33
窗口[ 1 , 3 ] [1,3][1,3]: 数据包为[ 2 : 3 , 3 : 7 , 4 : 6 ] [2:3, 3:7, 4:6][2:3,3:7,4:6]
2 : 3 2:32:3后面第一个优先级更高的是3 : 7 3:73:7，输出3 33
3 : 7 3:73:7后面没有优先级更高的，不输出
4 : 6 4:64:6后面没有优先级更高的，不输出
该窗口输出:3 33
窗口[ 2 , 4 ] [2,4][2,4]: 数据包为[ 3 : 7 , 4 : 6 , 5 : 4 ] [3:7, 4:6, 5:4][3:7,4:6,5:4]
3 : 7 3:73:7后面没有优先级更高的，不输出
4 : 6 4:64:6后面没有优先级更高的，不输出
5 : 4 5:45:4后面没有优先级更高的，不输出
该窗口无输出

样例2

输入

4 3 1:1 2:2 3:3 4:4

输出

2,3 3,4

说明

窗口[ 0 , 2 ] [0,2][0,2]: 数据包为[ 1 : 1 , 2 : 2 , 3 : 3 ] [1:1, 2:2, 3:3][1:1,2:2,3:3]
1 : 1 1:11:1后面第一个优先级更高的是2 : 2 2:22:2，输出2 22
2 : 2 2:22:2后面第一个优先级更高的是3 : 3 3:33:3，输出3 33
3 : 3 3:33:3后面没有优先级更高的，不输出
输出:2 223 33
窗口[ 1 , 3 ] [1,3][1,3]: 数据包为[ 2 : 2 , 3 : 3 , 4 : 4 ] [2:2, 3:3, 4:4][2:2,3:3,4:4]
2 : 2 2:22:2后面第一个优先级更高的是3 : 3 3:33:3，输出3 33
3 : 3 3:33:3后面第一个优先级更高的是4 : 4 4:44:4，输出4 44
4 : 4 4:44:4后面没有优先级更高的，不输出
输出:3 334 44

样例3

输入

4 3 4:4 3:3 2:2 1:1

输出

说明

窗口[ 0 , 2 ] [0,2][0,2]: 数据包为[ 4 : 4 , 3 : 3 , 2 : 2 ] [4:4, 3:3, 2:2][4:4,3:3,2:2]
4 : 4 4:44:4后面没有优先级更高的，不输出
3 : 3 3:33:3后面没有优先级更高的，不输出
2 : 2 2:22:2后面没有优先级更高的，不输出
该窗口不输出
窗口[ 1 , 3 ] [1,3][1,3]: 数据包为[ 3 : 3 , 2 : 2 , 1 : 1 ] [3:3, 2:2, 1:1][3:3,2:2,1:1]
3 : 3 3:33:3后面没有优先级更高的，不输出
2 : 2 2:22:2后面没有优先级更高的，不输出
1 : 1 1:11:1后面没有优先级更高的，不输出
该窗口不输出
所有窗口均无输出

样例4

输入

3 4 1:5 2:3 3:7

输出

说明

窗口大小4 > 4>4>数据包数量3 33，窗口无输出，无满足结果输出

题解

思路

思路：单调栈

1. 预处理:使用单调栈算法计算每个数据包右边第一个priority更高的数据包下标。具体逻辑为：

   1. 定义stk维持一个单调递减栈，栈中存储数据包下标。定义nextMaxIndex数组，存储每个位置右边第一个priority更高的数据包下标，开始所有值初始化为-1.
   2. 遍历输入数据包，遍历i时的处理逻辑：
      1. 递归维持栈递减，当栈非空，并且栈顶元素j小于当前数据优先级时，说明该位置为j右侧第一个大于它的下标，更新nextMaxIndex[j] = i,并弹出栈顶元素。
      2. 将i压入栈中，等待被处理。

2. 注意n < k时，直接返回为空即可。

3. 由于k <=100，可以枚举所有窗口，并求出每个窗口的结果序列，以这个{i, i + k -1}为例：

   1. 使用currentWindRes存储当前窗口结果。
   2. 确定窗口边界为windClose = i + k - 1
   3. 从前往后遍历{i, i + k -1}, 当前位置为j，如果nextMaxIndex[j] == -1或者nextMaxIndex[j] > windClose直接跳过(当前窗口内没有优先级更高)。否则加入{packets[j].id, packets[nextMaxIndex[j]].id}
   4. 按照3的逻辑处理之后，如果currentWindRes为空说明改窗口无输出，不添加进最终结果。

code

importjava.util.*;publicclassMain{publicstaticList<List<Integer>>priorityPackets(intn,intk,List<int[]>packets){List<List<Integer>>res=newArrayList<>();if(n<k)returnres;int[]nextMaxIndex=newint[n];Arrays.fill(nextMaxIndex,-1);Stack<Integer>stack=newStack<>();// 单调栈：找下一个更大值for(inti=0;i<n;i++){while(!stack.isEmpty()&&packets.get(i)[1]>packets.get(stack.peek())[1]){nextMaxIndex[stack.pop()]=i;}stack.push(i);}// 枚举窗口for(inti=0;i<=n-k;i++){intr=i+k-1;List<Integer>cur=newArrayList<>();for(intj=i;j<=r;j++){if(nextMaxIndex[j]!=-1&&nextMaxIndex[j]<=r){cur.add(packets.get(nextMaxIndex[j])[0]);}}if(!cur.isEmpty()){res.add(cur);}}returnres;}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=Integer.parseInt(sc.nextLine().trim());intk=Integer.parseInt(sc.nextLine().trim());String[]arr=sc.nextLine().trim().split(" ");List<int[]>packets=newArrayList<>();for(Strings:arr){String[]tmp=s.split(":");packets.add(newint[]{Integer.parseInt(tmp[0]),Integer.parseInt(tmp[1])});}List<List<Integer>>res=priorityPackets(n,k,packets);if(res.isEmpty())return;for(inti=0;i<res.size();i++){if(i>0)System.out.print(" ");for(intj=0;j<res.get(i).size();j++){if(j>0)System.out.print(",");System.out.print(res.get(i).get(j));}}}}