題目
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
.
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è)位置的水面高度，再由其求得水的體積骗爆。
而求水面高度嘶卧，則可分為兩種情況：
- 當(dāng)前位置后有大于等于當(dāng)前高度的位置喜爷，則自該位置起，將水面高度賦為當(dāng)前高度
- 當(dāng)前位置后沒有大于等于當(dāng)前高度的位置了，則自該位置之后，將水面高度賦為其之后的最高高度划栓。
由于這兩種情況都需要用到其后的最大高度，所以可以使用一個(gè)數(shù)組保存該值条获。另外別忘了每個(gè)位置的水面高度不能低于該位置的高度忠荞。
實(shí)現(xiàn)
class Solution {
public:
int trap(vector<int>& height) {
if(height.size()<=1) return 0;
int n = height.size();
int maxheight[n] = {0};
int maxpos[n] = {0};
int water[n] = {0};
maxheight[n-1] = height[n-1];
maxpos[n-1] = n-1;
for(int i=n-2; i>=0; i--){
if(height[i] >= maxheight[i+1]){
maxheight[i] = height[i];
maxpos[i] = i;
}
else{
maxheight[i] = maxheight[i+1];
maxpos[i] =maxpos[i+1];
}
}
int i=0;
while(i<n-1){
if(height[i]>=maxheight[i+1]){
water[i] = height[i];
for(int j=i+1; j<=maxpos[i+1]; j++){
water[j] = maxheight[i+1];
}
i = maxpos[i+1];
}
else{
int tmp = height[i];
while(i<n && height[i]<=tmp){
water[i] = tmp;
i++;
}
water[i] = height[i];
}
}
int ans = 0;
for(int i=0; i<n; i++){
ans += water[i] - height[i];
}
return ans;
}
};
思考
看了題解發(fā)現(xiàn)有更簡(jiǎn)單的思路：
- 掃描一遍， 找到最高的柱子月匣，該柱子將數(shù)組分成左右兩組
- 對(duì)于兩組分別處理
參考代碼
class Solution{
public:
int trap(const vector<int> &A){
const int n = A.size();
int max = 0; //最高的柱子钻洒，將數(shù)組分成兩半
for (int i = 0; i < n; i++)
if (A[i] > A[max])
max = i;
int water = 0;
for (int i = 0, peak = 0; i < max; i++)
if (A[i] > peak)
peak = A[i];
else
water += peak - A[i];
for (int i = n - 1, top = 0; i > max; i--)
if (A[i] > top)
top = A[i];
else
water += top - A[i];
return water;
}
};
