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.

这道题的做法在于找到最高的两根柱子,两根柱子中间的就是此片区域肯定有水的部分。

之后再用同样的方法计算此区域两边的两个区域最高柱子间的含水量,以此递归直到两根柱子相邻。

如[0,1,0,2,1,0,1,3,2,1,2,1], 则最高柱子为2和3,其位置分别为3和7,故计算3和7之间的含水量。

两边的区域分别为0->3和7->11,所以再同样做法求得这两片区域的最大柱间的含水量。以此递归最终可得结果6。

C code:

void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; }
void waterCal(int** height, const int left, const int right, int* water)
{
if(right - left < 2) return;

int first = 0, second = 0;
int newLeft = 0, newRight = 0;
for(int i = left; i <= right; ++i)
{
if((*height)[i] >= first) { second = first; first = (*height)[i]; newRight = newLeft; newLeft = i; }
else if((*height)[i] < first && (*height)[i] >= second) { second = (*height)[i]; newRight = i; }
}
if(newLeft > newRight) swap(&newLeft, &newRight);
int minHeight = second;
for(int i = newLeft + 1; i < newRight; ++i)
*water += second – (*height)[i];
waterCal(height, left, newLeft, water);
waterCal(height, newRight, right, water);
}

int trap(int* height, int heightSize) {
int water = 0;
waterCal(&height, 0, heightSize – 1, &water);
return water;
}

C++

class Solution {
public:
void swap(int& a, int& b) { int temp = a; a = b; b = temp; }
void waterCal(vector<int>& height, const int left, const int right, int& water)
{
if(right - left < 2) return;

int first = 0, second = 0;
int newLeft = 0, newRight = 0;
for(int i = left; i <= right; ++i)
{
if(height[i] >= first) { second = first; first = height[i]; newRight = newLeft; newLeft = i; }
else if(height[i] < first && height[i] >= second) { second = height[i]; newRight = i; }
}
if(newLeft > newRight) swap(newLeft, newRight);
int minHeight = second;
for(int i = newLeft + 1; i < newRight; ++i)
water += second – height[i];
waterCal(height, left, newLeft, water);
waterCal(height, newRight, right, water);
}

int trap(vector<int>& height) {
int water = 0;
waterCal(height, 0, height.size() – 1, water);
return water;
}
};

需要注意的一点是不要通过起伏变换来进行判断,如果遇到[5,2,1,2,1,5]这种两个高柱子间有起伏变化是难以判断的。

Leave a Reply

Your email address will not be published. Required fields are marked *