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!
題目大意：給以一個(gè)數(shù)組硬纤，每個(gè)元素表示長(zhǎng)方體的高糖荒，這些長(zhǎng)方體寬度為1雪侥，求這個(gè)數(shù)組的長(zhǎng)方體組成的圖形能蓄多少水
解題思路：當(dāng)前位置能蓄水要求兩邊的高度都高于當(dāng)前位置，所以我們掃描到當(dāng)前位置，只需判斷當(dāng)前位置是否對(duì)蓄的水有貢獻(xiàn)。
當(dāng)前位置寬度為1最終的貢獻(xiàn)值，為左邊高度的最大值和右邊高度的最大值宰僧，取其中最小的，然后和當(dāng)前高度相減观挎，如果大于0琴儿，則這個(gè)值就是貢獻(xiàn)值
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;
}
};
