给定 n 个非负整数表示每个宽度为 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：单调栈
解题思路：
对于低的柱子入栈，当出现比栈顶高的柱子，则认为可以进行一波计算。计算雨水的时候需要注意的是雨水区域的右边 r 指的自然是当前索引 i 底部是栈顶 ，因为遇到了更高的右边，所以它即将出栈，使用cur 来记录它，并让它出栈左边l 就是新的栈顶雨水的区域全部确定了，水坑的高度就是左右两边更低的一边减去底部，宽度是在左右中间使用乘法即可计算面积。
func trap(height []int) int {
stack := make([]int, 0)
ret := 0
for i := 0; i < len(height); i++ {
for len(stack) != 0 && height[stack[len(stack)-1]] < height[i] {
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack) == 0 {
break
}
h := height[i]
if height[stack[len(stack)-1]] < h {
h = height[stack[len(stack)-1]]
}
w := i - stack[len(stack)-1] - 1
ret += w * (h - height[cur])
}
stack = append(stack, i)
}
return ret
}
解法 2: 当前柱子能否蓄水，取决于左右的最大值和当前柱子的差值
func max_num(arr []int) int {
max := 0
for i:= 0; i< len(arr);i++ {
x := arr[i]
if x > max {
max = x
}
}
return max
}
func trap(height []int) int {
left_max_arr := make([]int, 0)
right_max_arr := make([]int, 0)
ret := 0
for i:=0;i<len(height);i++ {
left_max_arr = append(left_max_arr, max_num(height[:i]))
right_max_arr = append(right_max_arr, max_num(height[i:]))
}
for i:=0;i<len(height);i++ {
if left_max_arr[i] < right_max_arr[i] {
if left_max_arr[i]> height[i] {
ret += left_max_arr[i] - height[i]
}
}else{
if right_max_arr[i] > height[i] {
ret += right_max_arr[i] - height[i]
}
}
}
return ret
}
解法三：双指针解法
从上面的思路，很容易引出双指针解法，将算法的空间复杂度从 o (n) 降到 o (1)
func trap(height []int) int {
left := 0
right := len(height)-1
left_max := 0
right_max := 0
ret := 0
for left < right {
water_level := left_max
if left_max > right_max {
water_level = right_max
}
if height[left] <= water_level {
ret += water_level-height[left]
left += 1
continue
}
if height[right] <= water_level {
ret += water_level-height[right]
right -= 1
continue
}
if left_max < height[left] {
left_max = height[left]
}
if right_max < height[right] {
right_max = height[right]
}
}
return ret
}