42.H 接雨水

Problem: 42. 接雨水

思路

最简单的思路是，对于每个元素，都向左和向右找到最大值，然后二者中取最小值再减去当前元素的值，就是当前元素能接到的雨水量。但是这种方式的时间复杂度为O($N^2$)。

优化后的思路是动态规划。创建数组leftMax和rightMax用于存储左右两边的最大值。leftMax[i]表示第i个元素及其左边的最大值，rightMax[i]表示第i个元素及其右边的最大值。显然，leftMax[0] = 0, rightMax[len(height)-1] = 0, 而且有：

• leftMax[i] = max(leftMax[i-1], height[i])

• rightMax[i] = max(rightMax[i+1], height[i])

每个元素i可接到的雨水量为min(leftMax[i], rightMax[i]) - height[i]，最后做一下求和即可。

Code

func trap(height []int) int {
	leftMax := make([]int, len(height))
	leftMax[0] = height[0]
	for i := 1; i < len(height); i++ {
		leftMax[i] = max(leftMax[i-1], height[i])
	}

	rightMax := make([]int, len(height))
	rightMax[len(height)-1] = height[len(height)-1]
	for i := len(height) - 2; i >= 0; i-- {
		rightMax[i] = max(rightMax[i+1], height[i])
	}

	ans := 0
	for i, h := range height {
		ans += min(leftMax[i], rightMax[i]) - h
	}

	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}