大苹果
接雨水
给定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解法一:/***@param{number[]}height*@return{number}*/vartrap=function(height){letleft=0;letright=height.length-1;letsum=0;letleftMax=0;letrightMax=0;while(left<right){if(height[left]<=height[right]){if(height[left]>=leftMax){leftMax=height[left];}else{sum+=leftMax-height[left];}left++;}else{if(height[right]>=rightMax){rightMax=height[right];}else{sum+=rightMax-height[right];}right--;}}returnsum;};说明:要计算给定柱子高度图中的接雨水量,我们可以使用双指针的方法进行计算。这个问题通常被称为“接雨水问题”(TrappingRainWaterProblem)。方法:双指针算法步骤初始化指针和变量:左指针left指向数组的开始位置(索引0)。右指针right指向数组的结束位置(索引n-1)。初始化left_max和right_max分别为柱子高度的初始左端和右端。初始化water_trapped变量为0,用于存储总的接雨水量。遍历柱子高度数组:如果height[left]小于等于height[right]:否则:如果height[left]大于等于left_max,则更新left_max。否则,计算当前位置能接的水量为left_max-height[left],并将该水量累加到water_trapped。移动左指针,即left增加1。如果height[right]大于等于right_max,则更新right_max。否则,计算当前位置能接的水量为right_max-height[right],并将该水量累加到water_trapped。移动右指针,即right减少1。当left小于right时,进行以下操作:返回结果:当循环结束时,water_trapped即为接雨水的总量。算法实现下面是用Python实现的代码:deftrap(height):ifnotheight:return0left,right=0,len(height)-1left_max,right_max=height[left],height[right]water_trapped=0whileleft<right:ifheight[left]<=height[right]:ifheight[left]>=left_max:left_max=height[left]else:water_trapped+=left_max-height[left]left+=1else:ifheight[right]>=right_max:right_max=height[right]else:water_trapped+=right_max-height[right]right-=1returnwater_trapped#示例height=[0,1,0,2,1,0,1,3,2,1,2,1]result=trap(height)print("能接的雨水总量:",result)示例输入:height=[0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释在这个例子中,按照这种高度排列的柱子,经过雨水积累后,能够接住的雨水总量为6。复杂度分析时间复杂度:O(n),其中n是柱子高度数组的长度。我们只需遍历一次数组。空间复杂度:O(1),除了存储变量外,不需要额外的空间。这种方法有效地利用了双指针技巧,通过一次遍历即可完成对接雨水量的计算,是解决该问题的常用方法之一。
栈,数组,双指针,动态规划,单调栈
550
30天前