给定 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

解题思绪：

1，办法一：垂曲切割

A，关于肆意位置i，承接的雨水更大量是，位置i左侧的更大值和右侧更大值中较小者和位置i的高度差

B，因而需要两个预处置数组，记录位置i的左侧更大值和右侧更大值

2，办法二：程度切割

A，我们能够维护一个递加的栈

B，若是栈顶元素比比当前元素小，栈顶元素出栈

C，比力左侧元素和当前元素中间二者较小者

D，高度就是较小者和栈顶元素之差

E，宽度就是当前坐标和左侧坐标之间的间隔

3，办法三：双指针

A，能够比力摆布两个位置的值，较小者挪动指针

B，更新最左和最右的更大值，因为挪动指针的单调性，所以若是挪动的是左指针，当前左侧更大值必然比右侧更大值小

C，若是当前值比左侧更大值小，成果就取二者差值

代码实现

计划一：

func trap(height []int) int { leftMax:=make([]int,len(height)) rightMax:=make([]int,len(height)) leftMax[0]=height[0] rightMax[len(height)-1]=height[len(height)-1] for i:=1;i<len(height);i++{ if height[i]>leftMax[i-1]{ leftMax[i]=height[i] }else{ leftMax[i]=leftMax[i-1] } if height[len(height)-1-i]>rightMax[len(height)-i]{ rightMax[len(height)-1-i]=height[len(height)-1-i] }else{ rightMax[len(height)-1-i]=rightMax[len(height)-i] } } //fmt.PRintln(leftMax,rightMax) var ans int for i:=0;i<len(height);i++{ if leftMax[i]>rightMax[i]{ ans+=rightMax[i]-height[i] }else{ ans+=leftMax[i]-height[i] } } return ans}

计划二:

func trap(height []int) int { var stack []int ans:=0 for i,h:=range height{ for len(stack)>0 && height[stack[len(stack)-1]]<h{ top:=stack[len(stack)-1] stack=stack[:len(stack)-1] if len(stack)==0{ break } max:=stack[len(stack)-1] width:=i-max-1 if h<height[max]{ans+=width*(h-height[top]) }else{ans+=width*(height[max]-height[top]) } } stack=apPEnd(stack,i) } return ans}

计划三:

func trap(height []int) int { left:=0 right:=len(height)-1 leftMax:=left rightMax:=right ans:=0 for left<right{ if height[left]<height[right]{ if height[left]>height[leftMax]{ leftMax=left }else{ ans+=height[leftMax]-height[left] } left++ }else{ if height[right]>height[rightMax]{ rightMax=right }else{ ans+=height[rightMax]-height[right] } right-- } } return ans}