【leetcode】42.接雨水js

文章目录题目代码题目代码核心是短板原理接的雨水 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} */vartrapfunction(height){// 接的雨水 min(maxLeft, maxRight) - height[i]letmaxLeft0,maxRight0;letleft0,rightheight.length-1;letres0;while(leftright){if(height[left]height[right]){maxLeftMath.max(height[left],maxLeft);resmaxLeft-height[left];left;}else{maxRightMath.max(height[right],maxRight);resmaxRight-height[right];right--;}}returnres;};