42. 接雨水

42. 接雨水

暴力法

func trap(height []int)int{
    l :=len(height)
    res :=0
    // 起始位置是第一个，而不是0
    // 结束位置是倒数第二个，而不是倒数第一个
    for i:=1;i<l-1;i++{
        leftMax :=height[i]
        for k:=i-1;k>=0;k--{
            if leftMax<height[k]{
                leftMax = height[k]
            }
        }
        if leftMax<=height[i]{
            continue
        }
        rightMax :=height[i]
        for j:=i+1;j<l;j++{
            if rightMax<height[j]{
                rightMax = height[j]
            }
        }
        if rightMax<=height[i]{
            continue
        }
        minVal := min(leftMax,rightMax)
        water := minVal-height[i]
        res =res+water
    }
    return res
}
func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}

动态规划

动态规划实际上就是减少暴力中的重复计算问题。
leftDP 表示i 左边的最大值
rightDP表示以i开始右边的最大值

func trap(height []int)int{
    if len(height)==0{
        return 0
    }
    size :=len(height)
    res :=0
    leftDP :=make([]int,size)
    rightDP :=make([]int,size)
    leftDP[0]= height[0]
    rightDP[size-1] = height[size-1]
    for i:=1;i<size;i++{
        leftDP[i] = max(leftDP[i-1],height[i])
    }
    for i:=size-2;i>=0;i--{
        rightDP[i] = max(rightDP[i+1],height[i])
    }
    for i:=1;i<size-1;i++{
        minHeight := min(leftDP[i],rightDP[i])
        waterVal :=minHeight-height[i]
        res +=waterVal
    }
    return res
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}
func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}