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.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

第一答案未解出，以下是错误代码

classSolution{publicinttrap(int[]height){inti,j;intvolume=0;intmaxHeight=0;intmaxIndex=0;for(i=0;i<height.length;i++){if(height[i]>maxHeight){maxHeight=height[i];maxIndex=i;}}for(i=0;i<height.length-1;i++){j=i+1;if(height[i]==0){continue;}while(height[j]<height[i]&&i<maxIndex){volume+=height[i]-height[j];j++;if(j==height.length-1){break;}}i=j-1;ints_all=0,s_black=0;while(i>=maxIndex){if(height[j]<height[i]){for(intk=j;k<height.length;k++){if(i==height.length-2||k==height.length-2){break;}if(height[k+1]>height[k]){s_all=Math.min(height[k+1],height[i])*(k-i);volume+=(s_all-s_black);i=k;}else{s_black+=height[k];}}}if(i==height.length-2){break;}}}returnvolume;}}

初始解题思路是：从左往右依次遍历数组，如果有右边柱子低于左边柱子的情况，就说明可以积水，但是一开始遗漏了一个问题，就是整个数组中最高的柱子右边 ，这种解决方法不再适用，因为右边没有比最高柱子更高的柱子了，最高柱子右边又可能形成新的小凹槽，于是我把最高的柱子下标找出，右边单独处理这些特殊地形，一开始的想法是将遍历最高柱右边，如果出现了两高夹一或多矮的情况，就说明这两中间可以积水，但是太复杂，超时了。

AI优化后的简洁版答案，不会超时：

classSolution{publicinttrap(int[]height){if(height==null||height.length<3)return0;// 1. 找到最高点intmaxIndex=0;for(inti=1;i<height.length;i++){if(height[i]>height[maxIndex]){maxIndex=i;}}intvolume=0;// 2. 处理左半边（从左到右到最高点）intleftMax=height[0];for(inti=1;i<maxIndex;i++){if(height[i]>leftMax){leftMax=height[i];// 遇到更高的柱子，更新左边界}else{volume+=leftMax-height[i];// 当前柱子可以接雨水}}// 3. 处理右半边（从右到左到最高点）- 完全对称的处理intrightMax=height[height.length-1];for(inti=height.length-2;i>maxIndex;i--){if(height[i]>rightMax){rightMax=height[i];// 遇到更高的柱子，更新右边界}else{volume+=rightMax-height[i];// 当前柱子可以接雨水}}returnvolume;}}

思路：我的最高柱右半边处理过程过于复杂，其实只需要将左半边的处理逆应用在右半边，即从数组末尾向最高柱处理即可，并且左半边的处理方式也可以简化，不用for和while嵌套

leftMax 记录从左边到当前位置的最高柱子，遍历 maxIndex 左边的每个位置：

• 如果当前柱子比 leftMax 高，更新 leftMax（形成新的边界）

• 如果当前柱子比 leftMax 低，说明这里可以接雨水，雨水量 = leftMax - height[i]

双指针解法：

classSolution{publicinttrap(int[]height){// 边界条件：如果数组为空或长度小于3，无法形成凹槽接雨水if(height==null||height.length<3){return0;}intleft=0;// 左指针intright=height.length-1;// 右指针intleftMax=0;// 左边最大高度intrightMax=0;// 右边最大高度intvolume=0;// 总雨水量// 当左右指针没有相遇时继续while(left<right){// 情况1：左边柱子比右边矮if(height[left]<height[right]){// 如果当前左边高度大于等于左边最大高度，更新左边最大高度if(height[left]>=leftMax){leftMax=height[left];}// 否则，说明可以接雨水，雨水量 = 左边最大高度 - 当前高度else{volume+=leftMax-height[left];}// 左指针向右移动left++;}// 情况2：右边柱子比左边矮或相等else{// 如果当前右边高度大于等于右边最大高度，更新右边最大高度if(height[right]>=rightMax){rightMax=height[right];}// 否则，说明可以接雨水，雨水量 = 右边最大高度 - 当前高度else{volume+=rightMax-height[right];}// 右指针向左移动right--;}}returnvolume;}}

思路：使用左右双指针，并维护左右两侧的最大高度。当左边的柱子比右边矮时，就移动左指针。如果移动后遇到的柱子比之前记录的左边最高柱子矮，说明它的左右两边都有更高的柱子，因此可以积水，积水量由左边最高柱子决定。之后，更新左边最高柱子的记录。这个过程持续进行，直到左边出现一根柱子，其高度不低于右边的柱子，这时左边的积水区域暂告一段落，转而开始处理右边的区域，并遵循同样的逻辑。