题解 ：#NC128 接雨水问题#

描述
给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例1
输入： [3,1,2,5,2,4]
返回值：5
说明：数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水

示例2
输入： [4,5,1,3,2]
返回值：2

方法 : 图形填充法
由题意可知，因为是随机的数组arr，所以一定会出现不规则的图形，而要解决不规则的图形的方法，我们一般是用填充法来解决。即填充部分图形，使之变成规则的图形，方便我们计算。
上图如果填充完整，就会是一个完整的矩形，如下图

如上图所示 ，我们假定 数组的面积 S0 /雨水的面积 S1 /填充面积 S2 /填充面积 S3 , 那么就是要求解 S1 的值。
1.利用循环，先求左视图的面积 A = S0 + S1 + S3
2.利用循环，再求右视图的面积 B = S0 + S1 + S2
3.利用循环，三求最大矩形的面积 C = S0 + S1 + S2 + S3
最后用面积差，求得 雨水的面积 S1 = A + B - C - S0

核心代码 Python ：

class Solution:
    def maxWater(self , arr ):
        s = lmax = rmax = 0
        for i in range(len(arr)):
            if lmax < arr[i]:
               lmax = arr[i]  # 左循环
            if rmax < arr[len(arr) - 1 - i]:
               rmax = arr[len(arr) - 1 - i] # 右循环
            s += lmax + rmax - arr[i] # 每循环一次，做叠加，
        return s - max(arr)*len(arr) # 最大矩形的面积 C = max(arr)*len(arr)

时间复杂度O(0)
空间复杂度(2)