img

如图所示，蓝色区域就是☔️积水区，现在需要计算这个值。

思路

以最高的柱子P为终点，从左L向P移动。

  • 如果L右边的柱子L2的长度低于当前L的高度，那么在该柱子上可以累积array[L]-array[L2]的雨水量
  • 如果L右边的柱子L2的长度大于等于当前L的高度，那么，L-L2实际上已经形成了一个池塘了
  • 从L2开始往右寻找池塘，直至找到P

找到P之后，就不能这样找了，因为右边不存在可以与P形成池塘的柱子。所以，从最右边往左找，思路和上面一致。

代码

func trap(height []int) int {
	var trap, i, j, t, maxIndex int
	for i = 0; i < len(height); i = j {
		t = 0
		for j = i + 1; j < len(height); j++ {
			if height[j] < height[i] {
				t += height[i] - height[j]
			} else {
				maxIndex = j
				trap += t
				break
			}
		}
	}

	for i = len(height) - 1; i > maxIndex; i = j {
		t = 0
		for j = i - 1; j >= maxIndex; j-- {
			if height[j] < height[i] {
				t += height[i] - height[j]
			} else {
				trap += t
				break
			}
		}
	}
	return trap
}