42. 接雨水

每个柱子上的雨水 = min（柱子左边的最大值，柱子右边的最大值） - height[i]

func trap(_ height: [Int]) -> Int {

        var water = 0
        let len = height.count
        var leftValue = height[0]
        var rightArray = Array.init(repeating: 0, count: len)
        rightArray[len - 1] = height[len - 1]
        for i in (0..<len - 1).reversed() {
            rightArray[i] = max(rightArray[i + 1], height[i])
        }
        for i in 0..<len {
            leftValue = max(leftValue, height[i])
            water += min(leftValue,rightArray[i]) - height[i]
        }
       

        return water
    
    }

最后这种思路比较难想

func trap(_ height: [Int]) -> Int {

        let len = height.count
        var water = 0 ,lowerMax = 0 ,l = 0 ,r = len - 1

        while l < r {
            var lower = 0
            if height[l] <= height[r]  {
                lower = height[l]
                l += 1
            }else {
                lower = height[r]
                r -= 1
            }
            lowerMax = max(lowerMax, lower)
            water += lowerMax - lower

        }
       

        return water
    
    }