給定 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
}