接雨水

1. 题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

2. 思路

1. 双指针
   • 对于每个元素，往左走找到最大值，往右走找到最大值
   • 取两者较小者，减去当前元素的值即为该位置能接到的最大雨水量
   • 累加起来即可

3. 实现

3.1. 双指针（中心扩散）

func trap(height []int) int {
    res := 0
    for i := 0; i < len(height); i++ {
        maxLeft := height[i]
        for left := i; left >= 0; left--{
            maxLeft = max(maxLeft, height[left])
        }
        maxRight := height[i]
        for right := i; right < len(height); right++{
            maxRight = max(maxRight, height[right])
        }
        res += min(maxLeft,maxRight)-height[i]
    }
    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
}

4. 参考

• 接雨水 - 接雨水 - 力扣（LeetCode）