Leetcode:42 container water
问题的描述为： Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
思路：主要在于观察图形的规律，有两种情况，一中为凹，一种为凸 ，但是这样的判断代码写起来非常的复杂。可以换另外的一种思路，观察总体的情况。
具体的代码：
public int trap(int[] height) {
int n = height.length;
int[] left = new int[n];
int[] right = new int[n];
int leftMax = Integer.MIN_VALUE;
int rightMax = Integer.MIN_VALUE;
// construct left max (including self) array
for (int i = 0; i < n; i++) {
if (height[i] > leftMax) {
leftMax = height[i];
}
left[i] = leftMax;
}
// construct right max (including self) array
for (int i = n - 1; i >= 0; i--) {
if (height[i] > rightMax) {
rightMax = height[i];
}
right[i] = rightMax;
}
int water = 0;
// water trapped
for (int i = 0; i < n; i++) {
int min = Math.min(left[i], right[i]);
water += (min - height[i]);
}
return water;
}