LeetCode 42 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [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之后的最大值，用数组保存起来，大大简化了计算！
