day7-接雨水-困难

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例 1输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。示例 2输入height [4,2,0,3,2,5]输出9提示n height.length1 n 2 * 1040 height[i] 105第一答案未解出以下是错误代码classSolution{publicinttrap(int[]height){inti,j;intvolume0;intmaxHeight0;intmaxIndex0;for(i0;iheight.length;i){if(height[i]maxHeight){maxHeightheight[i];maxIndexi;}}for(i0;iheight.length-1;i){ji1;if(height[i]0){continue;}while(height[j]height[i]imaxIndex){volumeheight[i]-height[j];j;if(jheight.length-1){break;}}ij-1;ints_all0,s_black0;while(imaxIndex){if(height[j]height[i]){for(intkj;kheight.length;k){if(iheight.length-2||kheight.length-2){break;}if(height[k1]height[k]){s_allMath.min(height[k1],height[i])*(k-i);volume(s_all-s_black);ik;}else{s_blackheight[k];}}}if(iheight.length-2){break;}}}returnvolume;}}初始解题思路是从左往右依次遍历数组如果有右边柱子低于左边柱子的情况就说明可以积水但是一开始遗漏了一个问题就是整个数组中最高的柱子右边 这种解决方法不再适用因为右边没有比最高柱子更高的柱子了最高柱子右边又可能形成新的小凹槽于是我把最高的柱子下标找出右边单独处理这些特殊地形一开始的想法是将遍历最高柱右边如果出现了两高夹一或多矮的情况就说明这两中间可以积水但是太复杂超时了。AI优化后的简洁版答案不会超时classSolution{publicinttrap(int[]height){if(heightnull||height.length3)return0;// 1. 找到最高点intmaxIndex0;for(inti1;iheight.length;i){if(height[i]height[maxIndex]){maxIndexi;}}intvolume0;// 2. 处理左半边从左到右到最高点intleftMaxheight[0];for(inti1;imaxIndex;i){if(height[i]leftMax){leftMaxheight[i];// 遇到更高的柱子更新左边界}else{volumeleftMax-height[i];// 当前柱子可以接雨水}}// 3. 处理右半边从右到左到最高点- 完全对称的处理intrightMaxheight[height.length-1];for(intiheight.length-2;imaxIndex;i--){if(height[i]rightMax){rightMaxheight[i];// 遇到更高的柱子更新右边界}else{volumerightMax-height[i];// 当前柱子可以接雨水}}returnvolume;}}思路我的最高柱右半边处理过程过于复杂其实只需要将左半边的处理逆应用在右半边即从数组末尾向最高柱处理即可并且左半边的处理方式也可以简化不用for和while嵌套leftMax 记录从左边到当前位置的最高柱子遍历 maxIndex 左边的每个位置如果当前柱子比 leftMax 高更新 leftMax形成新的边界如果当前柱子比 leftMax 低说明这里可以接雨水雨水量 leftMax - height[i]双指针解法classSolution{publicinttrap(int[]height){// 边界条件如果数组为空或长度小于3无法形成凹槽接雨水if(heightnull||height.length3){return0;}intleft0;// 左指针intrightheight.length-1;// 右指针intleftMax0;// 左边最大高度intrightMax0;// 右边最大高度intvolume0;// 总雨水量// 当左右指针没有相遇时继续while(leftright){// 情况1左边柱子比右边矮if(height[left]height[right]){// 如果当前左边高度大于等于左边最大高度更新左边最大高度if(height[left]leftMax){leftMaxheight[left];}// 否则说明可以接雨水雨水量 左边最大高度 - 当前高度else{volumeleftMax-height[left];}// 左指针向右移动left;}// 情况2右边柱子比左边矮或相等else{// 如果当前右边高度大于等于右边最大高度更新右边最大高度if(height[right]rightMax){rightMaxheight[right];}// 否则说明可以接雨水雨水量 右边最大高度 - 当前高度else{volumerightMax-height[right];}// 右指针向左移动right--;}}returnvolume;}}思路使用左右双指针并维护左右两侧的最大高度。当左边的柱子比右边矮时就移动左指针。如果移动后遇到的柱子比之前记录的左边最高柱子矮说明它的左右两边都有更高的柱子因此可以积水积水量由左边最高柱子决定。之后更新左边最高柱子的记录。这个过程持续进行直到左边出现一根柱子其高度不低于右边的柱子这时左边的积水区域暂告一段落转而开始处理右边的区域并遵循同样的逻辑。