42. 接雨水

---

前言

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

0位置最左20位置最右是不可能留下水的
19位置的最大高度假设6,要结算算水量
需要求6的左边,右边部分的max,以13做瓶颈,
因为6它的左边这么多最大值还没看过，但它的最大值是17,恐怕它真实的左边最大值是大于17的。
而我右边的最大值，这可是个真实最大值，所以6位置的水量就是13-6= 7格子水
左边跟右边max谁小就先结算那边的水量

代码

	public static int trap(int[] arr) {
    
		if (arr == null || arr.length < 2) {
    
			return 0;
		}
		int N = arr.length;
		int L = 1;
		int leftMax = arr[0];
		int R = N - 2;
		int rightMax = arr[N - 1];
		int water = 0;
		while (L <= R) {
    
			if (leftMax <= rightMax) {
    
				water += Math.max(0, leftMax - arr[L]);
				leftMax = Math.max(leftMax, arr[L++]);
			} else {
    
				water += Math.max(0, rightMax - arr[R]);
				rightMax = Math.max(rightMax, arr[R--]);
			}
		}
		return water;
	}