题目链接
题目简介
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
题目分析
- 首先，我们分析，什么情况下可以接到雨水？
- 一个点是否能接到雨水，和
他自身以及左右的高度MAX有关 - 例如：
heught[1]这个点，我们可以发现，他的左边MAX = 1，右边MAX = 3，综合来看，我们求出（左边MAX 和右边MAX的最小值）减去height[i]即可
题目代码
public int trap(int[] height) { // 处理下特殊数据 if(height == null || height.length == 0){ return 0; } // 左边动态扫描一遍，右边动态扫描一遍 // Math.min(left_max, right.max) - height[i] int len = height.length; int[] left_max = new int[len]; left_max[0] = height[0]; for(int i = 1; i < len; i++){ left_max[i] = Math.max(height[i], left_max[i - 1]); } int[] right_max = new int[len]; right_max[len - 1] = height[len - 1]; for(int i = len - 2; i >= 0; i--){ right_max[i] = Math.max(right_max[i + 1], height[i]); } int res = 0; for(int i = 1; i < len; i++){ res = res + Math.min(right_max[i], left_max[i]) - height[i]; } return res; }
