42.接雨水
下面是解法:
1.分别从两个方向遍历,数组存储遍历过程中的最大值
2.再次遍历数组,根据木桶原理,取min(left max,right max)和当前高度做对比
(这里可以只用一个数组,还有优化空间)
func trap(nums []int) int {n := len(nums) // 获取长度lmx := make([]int,n) // 左边遍历, 存储max数组rmx := make([]int,n) // 右边遍历, 存储max数组res :=0 for i:=0;i<n;i++ {if i>0 {lmx[i] = max(lmx[i-1],nums[i])}else{lmx[i]=nums[i]}}for i:=n-1;i>=0;i-- {if i < n-1 {rmx[i]=max(rmx[i+1],nums[i])}else{rmx[i]=nums[i]}}for i:=0;i<n;i++ {mi := min(rmx[i],lmx[i])if mi > nums[i]{res += mi-nums[i]}}return res
}