端口流量统计2026 华为OD机试真题 4月26日华为OD上机新系统考试真题 100 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解题目描述给定一个整数数组p o r t R a t e s portRatesportRatesp o r t R a t e s [ i ] portRates[i]portRates[i]表示该端口第i ii分钟端口流量速率单位:b p s bpsbps。输入描述给定一个整数数组p o r t R a t e s portRatesportRatesp o r t R a t e s [ i ] portRates[i]portRates[i]表示该端口第i ii分钟端口流量速率单位:b p s bpsbps。输出描述返回一个数组 ratesStatratesStatratesStat[i]ratesStat[i] 表示多少分钟以后出现比当前更大的流量速率如果没有出现更大的流量速率则值为0。示例1输入730,740,750,710,690,720,760,730输出1,1,4,2,1,1,0,0说明输入数组第 0分钟端口流速是 730bps第 1 分钟端口流速是 740bps相差 1 分钟则返回数组第 0 个元素的值为 1输入数组第 2 分钟端口流速是 750 bps第 6 分钟端口流速是 760 bps相差 4 分钟则返回数组第 2 个元素的值为 4。示例2输入800输出0说明只有一个数据返回 0示例3输入800,700输出0,0说明只有两个元素后一个流量比第一个流量低返回 [0,0]示例4输入700,800输出1,0说明只有两个元素后一个流量比第一个流量高返回 [1,0]解题思路核心思想这道题本质上是经典的“下一个更大元素”Next Greater Element问题可以通过单调栈Monotonic Stack来高效求解。题目要求对于数组中的每一个元素找到其之后第一个比它大的元素并计算它们之间的索引差值。如果之后没有更大的元素则返回0。单调栈的思路如下维护一个单调递减的栈栈中存储元素的索引。从左到右遍历数组对于当前遍历到的元素rates[i]如果栈不为空且rates[i]大于栈顶索引对应的元素rates[stack.peek()]说明找到了栈顶元素的下一个更大元素。弹出栈顶索引idx此时idx的下一个更大元素就是rates[i]它们之间的距离就是i - idx。将结果数组ans[idx]更新为i - idx。循环执行上述出栈操作直到栈为空或当前元素不再大于栈顶元素。将当前元素的索引i压入栈中。遍历结束后栈中剩余的索引表示没有找到更大的元素其对应的结果应为0初始化时默认为0即可。复杂度分析时间复杂度O ( N ) O(N)O(N)其中N NN是数组的长度。虽然有一个嵌套的while循环但每个元素最多入栈一次出栈一次所以总的操作次数是2 N 2N2N时间复杂度为O ( N ) O(N)O(N)。空间复杂度O ( N ) O(N)O(N)。在最坏情况下例如数组是单调递减的所有元素的索引都会压入栈中因此栈的最大空间为O ( N ) O(N)O(N)。结果数组也需要O ( N ) O(N)O(N)的空间。Javaimportjava.util.Scanner;importjava.util.Stack;publicclassMain{publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);if(scanner.hasNextLine()){Stringinputscanner.nextLine().trim();if(input.isEmpty()){return;}// 将输入的字符串以逗号分隔并转换为整数数组String[]partsinput.split(,);intnparts.length;int[]ratesnewint[n];for(inti0;in;i){rates[i]Integer.parseInt(parts[i]);}// 结果数组默认初始化为0int[]ansnewint[n];// 单调栈用于存储元素的索引StackIntegerstacknewStack();// 遍历每个端口流量速率for(inti0;in;i){// 当栈不为空且当前遍历的速率大于栈顶索引对应的速率时while(!stack.isEmpty()rates[i]rates[stack.peek()]){intidxstack.pop();// 计算时间差并更新结果数组ans[idx]i-idx;}// 将当前元素的索引入栈stack.push(i);}// 输出结果以逗号分隔StringBuildersbnewStringBuilder();for(inti0;in;i){sb.append(ans[i]);if(i!n-1){sb.append(,);}}System.out.println(sb.toString());}scanner.close();}}Pythonimportsysdefmain():# 读取所有输入去除首尾空白字符input_strsys.stdin.read().strip()ifnotinput_str:return# 将输入的字符串按逗号分割并转换为整数列表rateslist(map(int,input_str.split(,)))nlen(rates)# 结果数组默认初始化为0ans[0]*n# 单调递减栈存储元素的索引stack[]# 遍历每个端口流量速率foriinrange(n):# 当栈不为空且当前元素大于栈顶索引对应的元素时whilestackandrates[i]rates[stack[-1]]:# 弹出栈顶索引idxstack.pop()# 当前索引与出栈索引的差值即为时间间隔ans[idx]i-idx# 将当前索引入栈stack.append(i)# 输出结果将结果数组按逗号连接为字符串print(,.join(map(str,ans)))if__name____main__:main()JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});rl.on(line,(line){lineline.trim();if(!line)return;// 将输入的字符串按逗号分割并转换为数字数组constratesline.split(,).map(Number);constnrates.length;// 初始化结果数组所有元素默认填充为0constansnewArray(n).fill(0);// 单调栈存储元素的索引conststack[];// 遍历所有的流量速率for(leti0;in;i){// 如果栈不为空且当前速率大于栈顶索引对应的速率while(stack.length0rates[i]rates[stack[stack.length-1]]){// 栈顶索引出栈constidxstack.pop();// 当前索引减去出栈索引即为相差的分钟数ans[idx]i-idx;}// 将当前元素的索引压入栈中stack.push(i);}// 打印结果以逗号连接console.log(ans.join(,));});C#includeiostream#includevector#includestring#includesstream#includestackusingnamespacestd;intmain(){string input;// 读取一行输入if(getline(cin,input)){if(input.empty())return0;vectorintrates;stringstreamss(input);string token;// 按逗号分割字符串并转换为整数存入数组while(getline(ss,token,,)){rates.push_back(stoi(token));}intnrates.size();// 结果数组初始化为0vectorintans(n,0);// 单调递减栈存储数组元素的索引stackintst;// 遍历整个速率数组for(inti0;in;i){// 若栈不为空且当前元素大于栈顶索引对应的元素while(!st.empty()rates[i]rates[st.top()]){// 弹出栈顶索引intidxst.top();st.pop();// 计算当前索引与栈顶索引的时间差ans[idx]i-idx;}// 当前索引入栈st.push(i);}// 输出结果数组用逗号连接for(inti0;in;i){coutans[i];if(i!n-1){cout,;}}coutendl;}return0;}Gopackagemainimport(bufiofmtosstrconvstrings)funcmain(){// 使用bufio读取整行输入scanner:bufio.NewScanner(os.Stdin)ifscanner.Scan(){input:strings.TrimSpace(scanner.Text())iflen(input)0{return}// 按逗号分割输入字符串parts:strings.Split(input,,)n:len(parts)rates:make([]int,n)// 将字符串数组转换为整数数组fori:0;in;i{rates[i],_strconv.Atoi(parts[i])}// 结果数组默认值为0ans:make([]int,n)// 栈用于存储索引stack:make([]int,0)// 遍历速率数组fori:0;in;i{// 如果栈不为空且当前元素大于栈顶索引对应的元素forlen(stack)0rates[i]rates[stack[len(stack)-1]]{// 弹出栈顶元素idx:stack[len(stack)-1]stackstack[:len(stack)-1]// 记录时间差ans[idx]i-idx}// 将当前索引压入栈stackappend(stack,i)}// 构造输出字符串用逗号连接结果数组result:make([]string,n)fori:0;in;i{result[i]strconv.Itoa(ans[i])}fmt.Println(strings.Join(result,,))}}C语言#includestdio.h#includestdlib.h#includestring.h#defineMAX_N100000intmain(){charinput[MAX_N*6];// 假设输入的总长度// 读取一行输入if(fgets(input,sizeof(input),stdin)){// 去除末尾的换行符input[strcspn(input,\n)]0;if(strlen(input)0){return0;}intrates[MAX_N];intn0;// 使用strtok按逗号分割字符串char*tokenstrtok(input,,);while(token!NULL){rates[n]atoi(token);tokenstrtok(NULL,,);}// 结果数组和栈使用动态分配或者直接用最大长度int*ans(int*)calloc(n,sizeof(int));int*stack(int*)malloc(n*sizeof(int));inttop-1;// 遍历速率数组for(inti0;in;i){// 当栈不为空且当前速率大于栈顶索引对应的速率while(top0rates[i]rates[stack[top]]){intidxstack[top--];// 记录距离ans[idx]i-idx;}// 当前索引入栈stack[top]i;}// 输出结果以逗号分隔for(inti0;in;i){printf(%d,ans[i]);if(i!n-1){printf(,);}}printf(\n);free(ans);free(stack);}return0;}完整用例用例1730,740,750,710,690,720,760,730用例2800用例3800,700用例4700,800用例5994,931,977,580,884,774,950,700,557,674,791,856,741,609,697用例6500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519用例7520,519,518,517,516,515,514,513,512,511,510,509,508,507,506,505,504,503,502,501用例8500,500,500,500,500,500,500,500,500,500用例9919,580,579,606,615,651,647,896,588,547,916,817,581,606,514,643,724,589,713,664,986,533,541,791,875,853,960,595,902,547,522,795,620,568,772,749,765,973,524,801,814,510,831,501,845,764,638,748,553,744用例104331,2243,7956,1852,7746,4524,5913,5183,4144,9494,4784,6865,5599,7758,9907,8321,9146,6887,3229,7917,6678,1359,7500,6344,3824,7476,6006,4078,3473,934,5174,7574,6559,7956,7270,172,9452,2739,2368,8155,3905,7545,4292,3611,4341,8215,8220,3474,4915,4540,3845,3044,1996,2391,1062,2487,421,9765,7211,4040,1635,4958,3554,8572,8531,7777,2307,1021,5526,3521,6034,6796,835,2547,5206,3840,3746,3231,40,8266,1955,9015,2803,2100,7136,2038,1675,3373,5158,3644,2033,8251,9381,475,9509,7720,1129,6935,2974,3730文章目录端口流量统计题目描述输入描述输出描述示例1示例2示例3示例4解题思路核心思想复杂度分析JavaPythonJavaScriptCGoC语言完整用例用例1用例2用例3用例4用例5用例6用例7用例8用例9用例10