下雨了，算法帮你算能接多少水 ☔

求解思路

这道题的关键在于理解每个位置能接多少水。

想象你站在某个位置i上，这个位置能接住的水量取决于什么呢?

其实就是左右两边的"围墙"能托住多高的水。

具体来说就是左右两边最高的柱子,其中，这两个高度中较矮的那个决定了水位线,然后用这个水位线减去当前位置的高度,就是这个位置能接的水量。

如果当前位置本身就比水位线高,那自然接不住水。

所以问题就转化成了:

对于每个位置,我们需要知道它左边的最大值和右边的最大值,然后取两者的较小值作为水位,最后累加每个位置能接的水量即可。

方法1

既然需要知道每个位置左右两边的最大值,最直接的想法就是提前算好。

publicstaticinttrap(int[]nums){intn=nums.length;int[]lmax=newint[n];int[]rmax=newint[n];// 计算每个位置左边的最大值lmax[0]=nums[0];for(inti=1;i<n;i++){lmax[i]=Math.max(lmax[i-1],nums[i]);}// 计算每个位置右边的最大值rmax[n-1]=nums[n-1];for(inti=n-2;i>=0;i--){rmax[i]=Math.max(rmax[i+1],nums[i]);}// 累加每个位置能接的水量intans=0;for(inti=1;i<n-1;i++){ans+=Math.max(0,Math.min(lmax[i-1],rmax[i+1])-nums[i]);}returnans;}

方法2

假设左边最大值小于等于右边最大值,那么左指针位置的接水量只取决于左边最大值,右边再高也没用。反之亦然。

publicstaticinttrap(int[]nums){intl=1,r=nums.length-2;intlmax=nums[0],rmax=nums[nums.length-1];intans=0;while(l<=r){if(lmax<=rmax){// 左边矮,左指针位置的水量确定ans+=Math.max(0,lmax-nums[l]);lmax=Math.max(lmax,nums[l++]);}else{// 右边矮,右指针位置的水量确定ans+=Math.max(0,rmax-nums[r]);rmax=Math.max(rmax,nums[r--]);}}returnans;}

如果觉得有帮助，欢迎点赞、关注、转发~