企业官网建设流程全解析

常州网站设计制作,阜宁网站制作价格,做个什么类型网站,微信的微网站模板下载不了求解思路 这道题的关键在于理解每个位置能接多少水。 想象你站在某个位置i上#xff0c;这个位置能接住的水量取决于什么呢? 其实就是左右两边的围墙能托住多高的水。 具体来说就是左右两边最高的柱子,其中#xff0c;这两个高度中较矮的那个决定了水位线,然后用…求解思路这道题的关键在于理解每个位置能接多少水。想象你站在某个位置i上这个位置能接住的水量取决于什么呢?其实就是左右两边的围墙能托住多高的水。具体来说就是左右两边最高的柱子,其中这两个高度中较矮的那个决定了水位线,然后用这个水位线减去当前位置的高度,就是这个位置能接的水量。如果当前位置本身就比水位线高,那自然接不住水。所以问题就转化成了:对于每个位置,我们需要知道它左边的最大值和右边的最大值,然后取两者的较小值作为水位,最后累加每个位置能接的水量即可。方法1既然需要知道每个位置左右两边的最大值,最直接的想法就是提前算好。publicstaticinttrap(int[]nums){intnnums.length;int[]lmaxnewint[n];int[]rmaxnewint[n];// 计算每个位置左边的最大值lmax[0]nums[0];for(inti1;in;i){lmax[i]Math.max(lmax[i-1],nums[i]);}// 计算每个位置右边的最大值rmax[n-1]nums[n-1];for(intin-2;i0;i--){rmax[i]Math.max(rmax[i1],nums[i]);}// 累加每个位置能接的水量intans0;for(inti1;in-1;i){ansMath.max(0,Math.min(lmax[i-1],rmax[i1])-nums[i]);}returnans;}方法2假设左边最大值小于等于右边最大值,那么左指针位置的接水量只取决于左边最大值,右边再高也没用。反之亦然。publicstaticinttrap(int[]nums){intl1,rnums.length-2;intlmaxnums[0],rmaxnums[nums.length-1];intans0;while(lr){if(lmaxrmax){// 左边矮,左指针位置的水量确定ansMath.max(0,lmax-nums[l]);lmaxMath.max(lmax,nums[l]);}else{// 右边矮,右指针位置的水量确定ansMath.max(0,rmax-nums[r]);rmaxMath.max(rmax,nums[r--]);}}returnans;}如果觉得有帮助欢迎点赞、关注、转发~