端口流量统华为OD机试真题 华为OD上机考试真题 4月26号 100分题型华为OD机试真题目录点击查看: 华为OD机试真题题库目录机考题库 算法考点详解题目描述给定一个整数数组 portRatesportRates[i] 表示该端口第 i分钟端口流量速率单位:bps。返回一个数组 ratesStatratesStat[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#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includemap #includestack using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vectorint split(const string str, const string delimiter) { vectorint 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; } vectorint StatPortRates(vectorint portRates) { int n portRates.size(); vectorint ratesStat(n, 0); // 单调递减栈 stackint 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); vectorint portRates split(input, ,); vectorint ratesStat StatPortRates(portRates); // 输出结果 int n ratesStat.size(); for (int i 0; i n; i) { cout ratesStat[i]; if (i ! n - 1) { cout ,; } } return 0; }JAVAimport java.util.*; public class Main { public static int[] statPortRates(int[] portRates) { int n portRates.length; int[] ratesStat new int[n]; // 单调递减栈存索引 DequeInteger 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(,); } } }Pythonimportsys# 单调栈求解defstat_port_rates(portRates):nlen(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_strsys.stdin.readline().strip()portRateslist(map(int,input_str.split(,)))resstat_port_rates(portRates)print(,.join(map(str,res)))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});functionstatPortRates(portRates){constnportRates.length;constratesStatnewArray(n).fill(0);// 单调递减栈存索引conststack[];for(letin-1;i0;i--){while(stack.lengthportRates[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){constportRatesline.split(,).map(Number);constresstatPortRates(portRates);console.log(res.join(,));});Gopackagemainimport(bufiofmtosstrconvstrings)// 单调栈求解funcstatPortRates(portRates[]int)[]int{n:len(portRates)ratesStat:make([]int,n)// 单调递减栈存索引stack:[]int{}fori:n-1;i0;i--{forlen(stack)0portRates[i]portRates[stack[len(stack)-1]]{stackstack[:len(stack)-1]}iflen(stack)0{ratesStat[i]stack[len(stack)-1]-i}else{ratesStat[i]0}stackappend(stack,i)}returnratesStat}funcmain(){reader:bufio.NewReader(os.Stdin)input,_:reader.ReadString(\n)inputstrings.TrimSpace(input)parts:strings.Split(input,,)portRates:make([]int,len(parts))fori:0;ilen(parts);i{portRates[i],_strconv.Atoi(parts[i])}res:statPortRates(portRates)fori:0;ilen(res);i{fmt.Print(res[i])ifi!len(res)-1{fmt.Print(,)}}}C语言#includestdio.h#includestdlib.h#includestring.h// 单调栈求解voidstatPortRates(int*portRates,intn,int*ratesStat){int*stack(int*)malloc(sizeof(int)*n);inttop-1;for(intin-1;i0;i--){while(top0portRates[i]portRates[stack[top]]){top--;}if(top0){ratesStat[i]stack[top]-i;}else{ratesStat[i]0;}stack[top]i;}free(stack);}intmain(){charinput[100000];fgets(input,sizeof(input),stdin);intportRates[100000];intn0;// 使用 strtok 分割char*tokenstrtok(input,,);while(token!NULL){portRates[n]atoi(token);tokenstrtok(NULL,,);}intratesStat[10000];statPortRates(portRates,n,ratesStat);for(inti0;in;i){printf(%d,ratesStat[i]);if(i!n-1)printf(,);}return0;}