LeetCode42 接雨水

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

image

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

这道题当年面试的时候遇到过，当时在面试官面前苦思冥想半个小时，还是不会写。。。最后勉强说了一点想出来的一点思路，面试果不其然的挂了。。。
如今刷LeetCode的时候又遇到，还是不会，但现在毕竟我也刷了100多到题了，有了一点点经验，就按当时思路继续往下想，
这一想不要紧，发现当时勉强说出来的那一点点思路也是错的。。。这就尴尬了，不知道那时候面试官是没发现呢，还是怕我伤心没忍心揭穿我。。。
往事不要再提。。。还是好好做题：
对我来说，这个问题的迷惑性在于：水是可以流动的！我脑子好像默认了水会流动这个事实，所以一直把各个柱子连起来考虑。。。但事实上，这个问题中水完全就是抽象的点而已，跟水本身的性质没有任何关系。

这道题的核心是：计算每个柱子可以接到的雨水量，再求和即可；而每个柱子能接到的雨水量，取决于它两边其他柱子的最大值中较小的一个
也就是说，其实每个柱子都是可以单独起来考虑的，每个柱子接到的雨水量，跟它相邻的柱子基本没有关系，或者说相邻的柱子并不起决定性作用，小坑可能是处在一个大坑的内部。所以如果从整体上考虑的话，情况相当复杂，有很多中情况。但如果单独考虑每个柱子的话，问题就简单了，就是上面的核心那句。
最后还是参考别人代码完成了这道题
Swift代码如下：

func trap(_ height: [Int]) -> Int {
        let n = height.count
        if n <= 2 { return 0 }
        var leftArray = [Int](repeating:0, count: n) //leftArray是保存height[i]左边最大值的数组
        var rightArray = [Int](repeating:0, count: n)//rightArray是保存height[i]右边边最大值的数组
        var maxLeft = 0
        for i in 0 ..< n {
            maxLeft = max(maxLeft, height[i])
            leftArray[i] = maxLeft
        }
        
        var maxRight = 0
        for i in (0 ..< n).reversed() {
            maxRight = max(maxRight, height[i])
            rightArray[i] = maxRight
        }
        
        var result = 0
        for i in 1 ..< n - 1 {
            if leftArray[i - 1] <= 0 || rightArray[i + 1] <= 0 {
                continue
            }
            let temp = min(leftArray[i - 1], rightArray[i + 1]) - height[i]
            if temp > 0 {
                result += temp
            }
        }
        return result
        
    }

注意：上面分别用一个for循环遍历出了i之前的最大值和i之后的最大值，用数组保存起来，大大简化了计算！