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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
rainwatertrap.png
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!
题目大意：给以一个数组，每个元素表示长方体的高，这些长方体宽度为1，求这个数组的长方体组成的图形能蓄多少水
解题思路：当前位置能蓄水要求两边的高度都高于当前位置，所以我们扫描到当前位置，只需判断当前位置是否对蓄的水有贡献。
当前位置宽度为1最终的贡献值，为左边高度的最大值和右边高度的最大值，取其中最小的，然后和当前高度相减，如果大于0，则这个值就是贡献值
C
int trap(int* height, int heightSize) {
int level = 0, water = 0;
while (heightSize--) {
int lower = *height < height[heightSize] ? *height++ : height[heightSize];
if (lower > level) level = lower;
water += level - lower;
}
return water;
}
C++：
class Solution {
public:
int trap(vector<int>& height) {
int water = 0;
int size = height.size();
for (int i = 1; i < size - 1; i++) {
int max_left = 0, max_right = 0;
for (int j = i; j >= 0; j--) { //Search the left part for max bar size
max_left = max(max_left, height[j]);
}
for (int j = i; j < size; j++) { //Search the right part for max bar size
max_right = max(max_right, height[j]);
}
water += min(max_left, max_right) - height[i];
}
return water;
}
};
