接雨水 - 困难 - 算法题 - 算法 - 计算机

给定 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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

	输入：height = [4,2,0,3,2,5]
	输出：9

提示：

题解

	/**
	* 标准解法
	*
	* height = [0,1,0,2,1,0,1,3,2,1,2,1]
	* 从左到右的最大高度
	* right = [0,1,1,2,2,2,2,3,3,3,3,3]
	* 从右到左的每一个的最大高度
	* left = [3,3,3,3,3,3,3,3,2,2,2,1]
	* 交集
	* result = min (right, left) - height
	* = [0,0,1,0,1,2,1,0,0,1,0,0]
	* @param height
	* @return
	*/
	public static int trap2(int[] height) {
	int n = height.length;
	if (n == 0) return 0;

	int[] left = new int[height.length];
	left[0] = height[0];
	for (int i = 1; i < n; i++){
	left[i] = Math.max(height[i], left[i - 1]);
	}

	int[] right = new int[height.length];
	right[n - 1] = height[n - 1];
	for (int j = n - 2; j >= 0; j--){
	right[j] = Math.max(height[j], right[j + 1]);
	}

	int result = 0;
	for (int i = 0; i < n; i++){
	result += Math.min(left[i], right[i]) - height[i];
	}
	return result;
	}

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water