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!
问题： 给定一个数组，每个元素表示海报高度，每个元素宽度均为 1 ，求这个数组能装多少雨水。
虽然这道题属于 two pointers 类型，不过我是用借助队列来解的。
可能是因为之前做过直方图相关的题目Largest Rectangle in Histogram ，这道题做起来感觉思路挺顺畅。将数组的值称为泥土体积。
- 对于从左往右的递增区间，装满雨水后的总体积 - 该区间的总泥土体积 = 该区间的总雨水
- 对于剩余的从右往左的递增区间，同样地，装满雨水后的总体积 - 该区间的总泥土体积 = 该区间的总雨水
对于题目中的例子而言，从左往右的递增区间是 [0,1,0,2,1,0,1,3 ], 剩余的从右往左的递增区间是 [ 3,2,1,2,1]。
class place{
public:
int idx;
int height;
place(int idx, int height){
this->idx = idx;
this->height = height;
}
};
int trap(vector<int>& height) {
if(height.size() == ){
return ;
}
// 计算从左往右的递增区间
queue<place*> qL;
place* tmpp = new place(, height[]);
qL.push(tmpp);
for (int i = ; i < height.size(); i++) {
if (height[i] >= qL.back()->height) {
place* tmpp = new place(i, height[i]);
qL.push(tmpp);
}
}
int totalRectL = ;
while (qL.size() > ) {
place* tmpp = qL.front();
qL.pop();
int len = qL.front()->idx - tmpp->idx;
totalRectL += (tmpp->height * len);
}
place* heighestL = qL.front();
qL.pop();
int earthAmtL = ;
for (int i = ; i < heighestL->idx; i++) {
earthAmtL += height[i];
}
int waterL = totalRectL - earthAmtL;
// 计算剩余的从右往左的递增区间
queue<place*> qR;
tmpp = new place((int)height.size()-,height[height.size()-]);
qR.push(tmpp);
for (int i = (int)height.size()-; i >= heighestL->idx; i--) {
if (height[i] >= qR.back()->height) {
tmpp = new place(i, height[i]);
qR.push(tmpp);
}
}
int rectR = ;
while (qR.size() > ) {
place* tmpp = qR.front();
qR.pop();
int len = tmpp->idx - qR.front()->idx;
rectR += tmpp->height * len;
}
place* heighestR = qR.front();
qR.pop();
int earthAmtR = ;
for (int i = (int)height.size()-; heighestR->idx < i ; i--) {
earthAmtR += height[i];
}
int waterR = rectR - earthAmtR;
int res = waterL + waterR;
return res;
}