数据包优先级窗口查找华为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:priorityid:priorityi 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 332 : 3 2:32:3后面第一个优先级更高的是3 : 7 3:73:7输出3 333 : 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 333 : 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 222 : 2 2:22:2后面第一个优先级更高的是3 : 3 3:33:3输出3 333 : 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 333 : 3 3:33:3后面第一个优先级更高的是4 : 4 4:44:4输出4 444 : 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 44数据包数量3 33窗口无输出无满足结果输出题解思路思路单调栈预处理:使用单调栈算法计算每个数据包右边第一个priority更高的数据包下标。具体逻辑为定义stk维持一个单调递减栈栈中存储数据包下标。定义nextMaxIndex数组存储每个位置右边第一个priority更高的数据包下标开始所有值初始化为-1.遍历输入数据包遍历i时的处理逻辑递归维持栈递减当栈非空并且栈顶元素j小于当前数据优先级时说明该位置为j右侧第一个大于它的下标更新nextMaxIndex[j] i,并弹出栈顶元素。将i压入栈中等待被处理。注意n k时直接返回为空即可。由于k 100可以枚举所有窗口并求出每个窗口的结果序列以这个{i, i k -1}为例使用currentWindRes存储当前窗口结果。确定窗口边界为windClose i k - 1从前往后遍历{i, i k -1}, 当前位置为j如果nextMaxIndex[j] -1或者nextMaxIndex[j] windClose直接跳过(当前窗口内没有优先级更高)。否则加入{packets[j].id, packets[nextMaxIndex[j]].id}按照3的逻辑处理之后如果currentWindRes为空说明改窗口无输出不添加进最终结果。codeimportjava.util.*;publicclassMain{publicstaticListListIntegerpriorityPackets(intn,intk,Listint[]packets){ListListIntegerresnewArrayList();if(nk)returnres;int[]nextMaxIndexnewint[n];Arrays.fill(nextMaxIndex,-1);StackIntegerstacknewStack();// 单调栈找下一个更大值for(inti0;in;i){while(!stack.isEmpty()packets.get(i)[1]packets.get(stack.peek())[1]){nextMaxIndex[stack.pop()]i;}stack.push(i);}// 枚举窗口for(inti0;in-k;i){intrik-1;ListIntegercurnewArrayList();for(intji;jr;j){if(nextMaxIndex[j]!-1nextMaxIndex[j]r){cur.add(packets.get(nextMaxIndex[j])[0]);}}if(!cur.isEmpty()){res.add(cur);}}returnres;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnInteger.parseInt(sc.nextLine().trim());intkInteger.parseInt(sc.nextLine().trim());String[]arrsc.nextLine().trim().split( );Listint[]packetsnewArrayList();for(Strings:arr){String[]tmps.split(:);packets.add(newint[]{Integer.parseInt(tmp[0]),Integer.parseInt(tmp[1])});}ListListIntegerrespriorityPackets(n,k,packets);if(res.isEmpty())return;for(inti0;ires.size();i){if(i0)System.out.print( );for(intj0;jres.get(i).size();j){if(j0)System.out.print(,);System.out.print(res.get(i).get(j));}}}}
