42. 接雨水

题目描述查看：https://leetcode-cn.com/problems/trapping-rain-water/

　　题目的意思是给定一个数组，数组值表示柱子的高度，问能盛多少水。

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

思路

　　按照列来看，每一列能盛多少水，取决于它左边柱子的最大值leftMax和右边柱子的最大值rightMax，leftMax和rightMax里小的那个又决定水能有多高（木桶，能装多少水，短的说了算）。根据这个思路，只要知道每个柱子左边的最大值leftMax和右边的最大值rightMax，就能求解能装多少水了。

leftMax和rightMax的求解

 1         leftMax[0] = height[0];
 2         rightMax[height.length-1] = height[height.length-1];
 3         //比当前柱子和前一个柱子的leftMax，找到当前柱子的左最大值
 4         for (int i = 1; i < height.length-1; i++) {
 5             leftMax[i] = Math.max(leftMax[i-1],height[i]);
 6         }
 7         //右最大值是从当前柱子往右比，所以要从最右边的开始求
 8         //比当前柱子和前一个柱子的rightMax，找到当前柱子的右最大值
 9         for (int i = height.length -2;i > 0; i--) {
10             rightMax[i] = Math.max(rightMax[i+1],height[i]);
11         }

边界条件

2个元素，没法装水。

if(height.length < 3)return 0;

3个元素，装水值取决于height[0]和height[2]的高度，如果height[1]>=min(height[0],height[2])，没法装水。

if(height.length == 3)return Math.min(height[0],height[2]) - height[1] > 0 ?Math.min(height[0],height[2]) - height[1]:0;

代码

 1     public int trap(int[] height) {
 2         int[] leftMax = new int[height.length];
 3         int[] rightMax = new int[height.length];
 4         if(height.length < 3)return 0;
 5         if(height.length == 3)return Math.min(height[0],height[2]) - height[1] > 0 ?Math.min(height[0],height[2]) - height[1]:0;
 6         int water = 0;
 7         leftMax[0] = height[0];
 8         rightMax[height.length-1] = height[height.length-1];
 9         //比当前柱子和前一个柱子的leftMax，找到当前柱子的左最大值
10         for (int i = 1; i < height.length-1; i++) {
11             leftMax[i] = Math.max(leftMax[i-1],height[i]);
12         }
13         //右最大值是从当前柱子往右比，所以要从最右边的开始求
14         //比当前柱子和前一个柱子的rightMax，找到当前柱子的右最大值
15         for (int i = height.length -2;i > 0; i--) {
16             rightMax[i] = Math.max(rightMax[i+1],height[i]);
17         }
18 
19         for (int i = 1; i < height.length - 1; i++) {
20             int h = Math.min(leftMax[i],rightMax[i]);
21             if(h > height[i])water += h- height[i];
22         }
23         return water;
24     }

42. 接雨水

思路

边界条件

代码