golang力扣leetcode 42.接雨水

42.接雨水

42.接雨水

题解

题目：一定一个数组，代码下标位置的高度，求最大接雨水量

思路：

暴力 O(n^2)

1.在当前位置，向左找最大高度，向右找最大高度，取两者较小的
2.用最大高度的较小值 ，减去当前位置的高度，即接雨水量

动态规划O(n)

1.在暴力解法中，每到一个新位置，都要重新查找一遍左右最大值
2.我们可以提前将每个位置的左右最大值找出来
3.找出来后一次遍历即可计算答案
4.从后往前遍历一次，记录左边最大值
5.从前往后遍历一次，记录右边最大值

单调栈

1.遍历数组的时候维护一个栈
2.如果当前高度小于等于栈顶，则入栈（意味着当前位置的雨水，被栈顶限制）
3.如果当前高度大于栈顶，则计算栈顶的积水量（当前与栈顶的前一个限定了栈顶的积水量），并弹出栈顶

双指针

1.左右指针指向最左边和最右边
2.如果height[l] < height[r]，则积水量是依赖于height[l]的
3.如果height[l] > height[r]，则积水量是依赖于height[r]的
4.假设现在是依赖于height[l]
5.如果height[l]>left_max,说明没有积水，更新left_max
6.如果height[l]<left_max,说明有积水，计算积水量，并且记得移动指针

代码

func trap(height []int) int {
	ans := 0
	n := len(height)
	for i := 0; i < n; i++ {
		lH, rH := 0, 0
		for j := i; j >= 0; j-- {
			lH = max(lH, height[j])
		}
		for j := i; j < n; j++ {
			rH = max(rH, height[j])
		}
		ans += min(lH, rH) - height[i]
	}
	return ans
}
func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}
func min(i, j int) int {
	if i > j {
		return j
	}
	return i
}

func trap(height []int) int {
	ans, cnt := 0, 0
	n := len(height)
	lH, rH := make([]int, n), make([]int, n)
	for i := 0; i < n; i++ {
		cnt = max(cnt, height[i])
		rH[i] = cnt
	}
	cnt = 0
	for i := n - 1; i >= 0; i-- {
		cnt = max(cnt, height[i])
		lH[i] = cnt
	}
	for i := 0; i < n; i++ {
		ans += min(lH[i], rH[i]) - height[i]
	}
	return ans
}
func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}
func min(i, j int) int {
	if i > j {
		return j
	}
	return i
}

func trap(height []int) int {
	ans := 0
	stack := make([]int, 0)
	for i, h := range height {
		for len(stack) > 0 && h > height[stack[len(stack)-1]] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(stack) > 0 {
				break
			}
			left := stack[len(stack)-1]
			curWidth := i - left - 1
			curHeight := min(height[left], h) - height[top]
			ans += curWidth * curHeight
		}
		stack = append(stack, i)
	}
	return ans
}
func min(i, j int) int {
	if i > j {
		return j
	}
	return i
}

func trap(height []int) int {
	ans, n := 0, len(height)
	l, r := 0, n-1
	leftHeight, rightHeight := 0, 0
	for l < r {
		if height[l] < height[r] {
			if height[l] > leftHeight { //当前高度比左侧最高还高，则更新左侧最高
				leftHeight = height[l]
			} else { //当前高度比左侧最高 低， 说明构成凹槽，计算积水量
				ans += leftHeight - height[l]
			}
			l++
		} else {
			if height[r] > rightHeight {//当前高度比右侧最高还高，则更新右侧最高
				rightHeight = height[r]
			} else {//当前高度比右侧最高 低，说明构成凹槽，计算积水量
				ans += rightHeight - height[r]
			}
			r--
		}
	}
	return ans
}