华为非AI方向笔试真题 7月15号【水槽存水】

水槽存水(C/Py/Java/Js/Go)题解华为笔试真题 7月15号 非AI方向第一题 100分题型题目内容有一条直线水槽左右两端始终开口无挡板水可从两端流走水槽中从左到右插入了nnn块竖直挡板第iii块挡板高度为h[i]h[i]h[i]挡板厚度忽略不计。相邻两块挡板之间形成一个槽位槽底面积为111一共存在n−1n-1n−1个槽位。近期持续下雨每个槽位都能接收到充足的雨水直到水面稳定。对于槽位iii挡板iii与i1i1i1之间由于槽底面积为111故槽位的存水量数值等于其水面高度如果只有一个挡板则无法形成槽位其存水量为000。如下图所示555块挡板形成444个槽位以槽位333的存水量计算为例槽位333的水面高度受挡板222高度222和挡板555高度555影响水面高度为222故槽位333的存水量为222。输入描述第一行一个整数nnn1≤n≤300001 \le n \le 300001≤n≤30000表示挡板个数第二行nnn个整数h[1],h[2],...,h[n]h[1],h[2],...,h[n]h[1],h[2],...,h[n]1≤h[i]≤300001 \le h[i] \le 300001≤h[i]≤30000表示从左往右的每个挡板高度输出描述一个整数输出水槽水面稳定后所有槽位的总存水量样例1输入5 1 2 3 4 5输出10说明一共555个挡板可以形成444个槽位从左往右每个槽位存水量情况说明如下槽位111的存水量为111槽位222的存水量为222槽位333的存水量为333槽位444的存水量为444总存水量123410123410123410样例2输入6 3 1 2 5 4 5输出19说明一共666个挡板可以形成555个槽位从左往右每个槽位存水量情况说明如下 槽位111的存水量为333 槽位222的存水量为333 槽位333的存水量为333 槽位444的存水量为555 槽位555的存水量为555 总存水量333551933355193335519题解和思路思路实现思路模拟每个槽位能存储数量等于min(maxL, maxR)决定根据1的分析处理每个槽左侧/右侧最高挡板高度然后从前往后遍历确定每个操作能存水高度累加即可。算法平均时间复杂为O(n)C#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cinn;vectorinth(n);for(inti0;in;i){cinh[i];}// 没有槽位if(n1){cout0;return0;}// leftMax[i]第i块挡板左侧包括自己的最高挡板vectorintleftMax(n);leftMax[0]h[0];for(inti1;in;i){leftMax[i]max(leftMax[i-1],h[i]);}// rightMax[i]第i块挡板右侧包括自己的最高挡板vectorintrightMax(n);rightMax[n-1]h[n-1];for(intin-2;i0;i--){rightMax[i]max(rightMax[i1],h[i]);}longlongans0;// 枚举每个槽位挡板i与挡板i1之间for(inti0;in-1;i){ansmin(leftMax[i],rightMax[i1]);}coutans;return0;}Javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();int[]hnewint[n];for(inti0;in;i){h[i]sc.nextInt();}// 没有槽位if(n1){System.out.print(0);return;}// leftMax[i]第i块挡板左侧包括自己的最高挡板int[]leftMaxnewint[n];leftMax[0]h[0];for(inti1;in;i){leftMax[i]Math.max(leftMax[i-1],h[i]);}// rightMax[i]第i块挡板右侧包括自己的最高挡板int[]rightMaxnewint[n];rightMax[n-1]h[n-1];for(intin-2;i0;i--){rightMax[i]Math.max(rightMax[i1],h[i]);}longans0;// 枚举每个槽位挡板i与挡板i1之间for(inti0;in-1;i){ansMath.min(leftMax[i],rightMax[i1]);}System.out.print(ans);}}pythondefmain():nint(input())hlist(map(int,input().split()))# 没有槽位ifn1:print(0,end)return# leftMax[i]第i块挡板左侧包括自己的最高挡板leftMax[0]*n leftMax[0]h[0]foriinrange(1,n):leftMax[i]max(leftMax[i-1],h[i])# rightMax[i]第i块挡板右侧包括自己的最高挡板rightMax[0]*n rightMax[n-1]h[n-1]foriinrange(n-2,-1,-1):rightMax[i]max(rightMax[i1],h[i])ans0# 枚举每个槽位挡板i与挡板i1之间foriinrange(n-1):ansmin(leftMax[i],rightMax[i1])print(ans,end)if__name____main__:main()Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,(line){input.push(line);});rl.on(close,(){constnNumber(input[0]);consthinput[1].split( ).map(Number);// 没有槽位if(n1){console.log(0);return;}// leftMax[i]第i块挡板左侧包括自己的最高挡板constleftMaxnewArray(n);leftMax[0]h[0];for(leti1;in;i){leftMax[i]Math.max(leftMax[i-1],h[i]);}// rightMax[i]第i块挡板右侧包括自己的最高挡板constrightMaxnewArray(n);rightMax[n-1]h[n-1];for(letin-2;i0;i--){rightMax[i]Math.max(rightMax[i1],h[i]);}letans0;// 枚举每个槽位挡板i与挡板i1之间for(leti0;in-1;i){ansMath.min(leftMax[i],rightMax[i1]);}process.stdout.write(ans.toString());});Gopackagemainimport(bufiofmtos)funcmax(a,bint)int{ifab{returna}returnb}funcmin(a,bint)int{ifab{returna}returnb}funcmain(){in:bufio.NewReader(os.Stdin)varnintfmt.Fscan(in,n)h:make([]int,n)fori:0;in;i{fmt.Fscan(in,h[i])}// 没有槽位ifn1{fmt.Print(0)return}// leftMax[i]第i块挡板左侧包括自己的最高挡板leftMax:make([]int,n)leftMax[0]h[0]fori:1;in;i{leftMax[i]max(leftMax[i-1],h[i])}// rightMax[i]第i块挡板右侧包括自己的最高挡板rightMax:make([]int,n)rightMax[n-1]h[n-1]fori:n-2;i0;i--{rightMax[i]max(rightMax[i1],h[i])}varansint64// 枚举每个槽位挡板i与挡板i1之间fori:0;in-1;i{ansint64(min(leftMax[i],rightMax[i1]))}fmt.Print(ans)}