42. 接雨水

https://leetcode-cn.com/problems/trapping-rain-water/

解法一：暴力

本题与11.盛最多水的容器 类似。

虽然暴力，但很巧妙。i遍历一次数组，每次以i为中心，用指针j向两侧遍历，找左右最高的数maxleft和maxright，则i处能留下的雨水最多为：左右max的最小值减去i处的高度（可以理解为宽度为1的水柱）。

复杂度o(n^2)，c++没超时，py却超时了

class Solution {
public:
    int trap(vector<int>& height) {
    int ans = 0;
    int size = height.size();
    for (int i = 1; i < size - 1; i++) {
        int max_left = 0, max_right = 0;
        for (int j = i; j >= 0; j--) { //Search the left part for max bar size
            max_left = max(max_left, height[j]);
        }
        for (int j = i; j < size; j++) { //Search the right part for max bar size
            max_right = max(max_right, height[j]);
        }
        ans += min(max_left, max_right) - height[i];
    }
    return ans;
}
};

解法二：dp

与暴力的思路类似，不同在于求左右最高时可以使用之前的结果（dp）

用两个长度为n的一维数组leftMax和rightMax记录位置i的左右最大信息。易知i的左侧最大值为height[i]与i-1的leftMax中的较大者，同理i的右侧最大值为height[i]与i+1的rightMax中的较大者。

填好信息表后一次遍历，跟思路1一样每次统计i出的水量并累加即可。复杂度O（n)

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n <= 2:
            return 0
        leftMax, rightMax = [0]*n, [0]*n  #左右最高信息表
        leftMax[0], rightMax[n-1] = height[0], height[n-1]  #初始值
        #从左向右填表
        for i in range(1, n):
            leftMax[i] = max(leftMax[i-1], height[i])
        #从右向左填表        
        for i in range(n-2, -1, -1):
            rightMax[i] = max(rightMax[i+1], height[i])
        #一次遍历
        water = 0        
        for i in range(n):
            water += min(leftMax[i], rightMax[i]) - height[i]
        return water

另一种思路（2020.3.27）

left[i]表示i左侧最高的元素，初始left[0]=0，因为0处左侧没有任何阻挡，易知left[i] = max(left[i-1], height[i-1])，即i处左侧最高的阻挡为i左侧最高纪录与i-1处高度的较大者。right[i]表示i右侧最高，推导类似。

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left = [0] * n
        right = [0] * n
        for i in range(1, n):
            left[i] = max(left[i-1], height[i-1])
        for i in range(n-2, -1, -1):
            right[i] = max(right[i+1], height[i+1])
        res = 0
        for i in range(n):
            res += max(min(left[i], right[i]) - height[i], 0)    #排除负数
        return res