文章目录
- 题目
- 代码
题目
代码
核心是短板原理：
接的雨水 = min(maxLeft, maxRight) - height[i]
但要怎么体现在代码里呢？一开始想的是Math.min()，但学习的时候发现题解里min的影都没见到，而是对比height[left]和height[right]就可以实现对maxLeft和maxRight的对比。解释如下（来自d老师）：
当你确定某一边是短板时，你就能断定：这一侧当前的 Max（最大值）一定就是全局的 min。
我们分情况证明（以左边为例）：
当height[left] < height[right]成立时（左边是短板）：
- 因为
rightMax >= height[right]（右侧最大值至少是当前这根右柱子），所以rightMax > height[left]。 - 关键来了：此时
leftMax必然小于或等于rightMax。
为什么？用反证法——如果左边的最大值（leftMax）比右边的最大值（rightMax）还大，说明左边有一堵“超级高墙”。按照“移动短板”的规则，当指针还停留在那堵超级高墙时，因为它比右边的所有墙都高，算法会一直移动右指针向左靠拢，直到左右指针相遇，游戏结束——左指针压根儿没机会走到现在这个位置。
既然左指针走到了这里，就说明左边不存在比右边整体更高的墙，所以leftMax <= rightMax。
/** * @param {number[]} height * @return {number} */vartrap=function(height){// 接的雨水 = min(maxLeft, maxRight) - height[i]letmaxLeft=0,maxRight=0;letleft=0,right=height.length-1;letres=0;while(left<right){if(height[left]<height[right]){maxLeft=Math.max(height[left],maxLeft);res+=maxLeft-height[left];left++;}else{maxRight=Math.max(height[right],maxRight);res+=maxRight-height[right];right--;}}returnres;};
