华为OD新系统机试真题-端口流量统计(C/C++/Py/Java/Js/Go)
端口流量统
华为OD机试真题 华为OD上机考试真题 4月26号 100分题型
华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解
题目描述
给定一个整数数组 portRates，portRates[i] 表示该端口第 i分钟端口流量速率（单位:bps）。
返回一个数组 ratesStat，ratesStat[i] 表示多少分钟以后出现比当前更大的流量速率，如果没有出现更大的流量速率，则值为0。
输入描述
输入给定的整数数组，数字以逗号分割。
输出描述
输出所需ratesStat，数字以逗号分割。
用例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
题解
思路：单调栈
这类题属于
单调栈的模板题，遇到求每个元素之后/之前比当前大/小的题型时可以考虑使用单带栈算法解决。本题实际要求
多少分钟以后出现比当前更大的流量速率比较推荐使用从后往前进行处理，并且维持一个递减栈。栈中存储元素下标方便进行间隔时间计算。具体逻辑遍历当前元素
portRates[i]时:首先递归弹出栈中小于等于当前元素的数据。
如果此时栈为空，说明后续没有比当前元素大的，设置
ratesStat[i]为0，否则设置ratesStat[i] = stk.top() - i将当前下标压入栈中
按照3的逻辑即可得到正确结果，返回结果数组即可。
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> #include<stack> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<int> split(const string& str, const string& delimiter) { vector<int> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(stoi(str.substr(start, end - start))); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(stoi(str.substr(start))); return result; } vector<int> StatPortRates(vector<int>& portRates) { int n = portRates.size(); vector<int> ratesStat(n, 0); // 单调递减栈 stack<int> stk; for (int i = n - 1; i >= 0; i--) { while (!stk.empty() && portRates[i] >= portRates[stk.top()]) { stk.pop(); } if (stk.empty()) { ratesStat[i] = 0; } else { ratesStat[i] = (stk.top() - i); } stk.push(i); } return ratesStat; } int main() { string input; getline(cin, input); vector<int> portRates = split(input, ","); vector<int> ratesStat = StatPortRates(portRates); // 输出结果 int n = ratesStat.size(); for (int i = 0; i < n; i++) { cout << ratesStat[i]; if (i != n - 1) { cout << ","; } } return 0; }JAVA
import java.util.*; public class Main { public static int[] statPortRates(int[] portRates) { int n = portRates.length; int[] ratesStat = new int[n]; // 单调递减栈（存索引） Deque<Integer> stack = new ArrayDeque<>(); for (int i = n - 1; i >= 0; i--) { while (!stack.isEmpty() && portRates[i] >= portRates[stack.peek()]) { stack.pop(); } if (!stack.isEmpty()) { ratesStat[i] = stack.peek() - i; } else { ratesStat[i] = 0; } stack.push(i); } return ratesStat; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String input = sc.nextLine(); String[] parts = input.split(","); int[] portRates = new int[parts.length]; for (int i = 0; i < parts.length; i++) { portRates[i] = Integer.parseInt(parts[i]); } int[] res = statPortRates(portRates); for (int i = 0; i < res.length; i++) { System.out.print(res[i]); if (i != res.length - 1) System.out.print(","); } } }Python
importsys# 单调栈求解defstat_port_rates(portRates):n=len(portRates)ratesStat=[0]*n# 单调递减栈（存索引）stack=[]foriinrange(n-1,-1,-1):whilestackandportRates[i]>=portRates[stack[-1]]:stack.pop()ifstack:ratesStat[i]=stack[-1]-ielse:ratesStat[i]=0stack.append(i)returnratesStat# 读取输入input_str=sys.stdin.readline().strip()portRates=list(map(int,input_str.split(",")))res=stat_port_rates(portRates)print(",".join(map(str,res)))JavaScript
constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});functionstatPortRates(portRates){constn=portRates.length;constratesStat=newArray(n).fill(0);// 单调递减栈（存索引）conststack=[];for(leti=n-1;i>=0;i--){while(stack.length&&portRates[i]>=portRates[stack[stack.length-1]]){stack.pop();}if(stack.length){ratesStat[i]=stack[stack.length-1]-i;}else{ratesStat[i]=0;}stack.push(i);}returnratesStat;}rl.on('line',function(line){constportRates=line.split(',').map(Number);constres=statPortRates(portRates);console.log(res.join(','));});Go
packagemainimport("bufio""fmt""os""strconv""strings")// 单调栈求解funcstatPortRates(portRates[]int)[]int{n:=len(portRates)ratesStat:=make([]int,n)// 单调递减栈（存索引）stack:=[]int{}fori:=n-1;i>=0;i--{forlen(stack)>0&&portRates[i]>=portRates[stack[len(stack)-1]]{stack=stack[:len(stack)-1]}iflen(stack)>0{ratesStat[i]=stack[len(stack)-1]-i}else{ratesStat[i]=0}stack=append(stack,i)}returnratesStat}funcmain(){reader:=bufio.NewReader(os.Stdin)input,_:=reader.ReadString('\n')input=strings.TrimSpace(input)parts:=strings.Split(input,",")portRates:=make([]int,len(parts))fori:=0;i<len(parts);i++{portRates[i],_=strconv.Atoi(parts[i])}res:=statPortRates(portRates)fori:=0;i<len(res);i++{fmt.Print(res[i])ifi!=len(res)-1{fmt.Print(",")}}}C语言
#include<stdio.h>#include<stdlib.h>#include<string.h>// 单调栈求解voidstatPortRates(int*portRates,intn,int*ratesStat){int*stack=(int*)malloc(sizeof(int)*n);inttop=-1;for(inti=n-1;i>=0;i--){while(top>=0&&portRates[i]>=portRates[stack[top]]){top--;}if(top>=0){ratesStat[i]=stack[top]-i;}else{ratesStat[i]=0;}stack[++top]=i;}free(stack);}intmain(){charinput[100000];fgets(input,sizeof(input),stdin);intportRates[100000];intn=0;// 使用 strtok 分割char*token=strtok(input,",");while(token!=NULL){portRates[n++]=atoi(token);token=strtok(NULL,",");}intratesStat[10000];statPortRates(portRates,n,ratesStat);for(inti=0;i<n;i++){printf("%d",ratesStat[i]);if(i!=n-1)printf(",");}return0;}