LeetCode Trapping Rain Water等雨水的凹槽容量

Givennnon-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], return6.

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 Marcosfor contributing this image!

最后黑体字的Thanks Marcos的意思是让我们放大我们的想象力，因为上图很容易误导我们的。如果只有上图的情况的话，我们可以很好用贪心法解决，但是，用贪心法是会出错的，因为如果我们计算当前最低点，然后往两边扩展找到两边递增的最高点，那么这个最高点很可能是局部最高点，答案就会出错。

有两个解题思路：

1 两边往中间搜索

2 由左往右搜索，跳跃式计算

如下面的分析图，会比较直观：

蓝色代表水，可以看见很多局部最高点都被水淹了。

这里计算面积不用一般几何书的方法，这里是两边往中间遍历，记录当前第二高点secHight，然后利用这个第二高点减去当前历经的柱子，剩下就装水容量了。

为什么是第二高点？因为两边比较，最高的点不用动，只移动第二高点。

第一个思路，按照上图的思想就能写出非常简洁的程序了，时间复杂度为O(n)：

int trap(int A[], int n) {
		int secHight = 0;
		int left = 0;
		int right = n-1;
		int area = 0;
		while (left < right){
			if (A[left] < A[right]){
				secHight = max(A[left], secHight);
				area += secHight-A[left];//计算当前格的能装雨水的容量
				left++;
			} else {
				secHight = max(A[right], secHight);
				area += secHight-A[right];
				right--;
			}
		}
		return area;
	}

第二个思路，这个思路不难，但是分情况太多，会搞的很复杂，所以有兴趣的挑战一下，不推荐使用。时间复杂度也是O(n)，可以AC。

class Solution {
public:
	int trap(int A[], int n) {
		int area = 0;
		int begin = 0;
		while (begin < n-1 && A[begin] <= A[begin+1]) begin++;
		while (begin < n)
			area += calculate(A, begin, n);
		return area;
	}

	//前跃思想
	int calculate(int A[], int &begin, int n)
	{
		int lowest = -1;
		int highest = -1;
		int i = 0;
		//找最低点；也可以不用找最低点；找最低点可以优化一个特殊情况：后面很长的降序序列
		for (i = begin; i < n-1; i++)
			if (A[i] < A[i+1])
			{
				lowest = i;
				break;//注意：记得break掉
			}
		//处理到了结尾的情况
		if (lowest == -1)
		{
			begin = n;
			return 0;
		}
		//找比begin还高的高点
		int tempHight = -1;
		int tempMax = -1;
		for (i = lowest+1; i < n; i++)
		{
			if (A[i] > A[begin]) 
			{
				highest = i;
				break;
			}
			//存储当前找到的最高度
			if (A[i] >= tempMax)
			{
				tempHight = i;
				tempMax = A[i];
			}
		}
		//搜索到最后，没有高于begin的
		if (i == n && n-1 != highest)
		{
			if (tempMax <= A[n-1])
				highest = n-1;
			else highest = tempHight;
		}
		//计算宽度
		int width = highest - begin - 1;
		//计算高度
		int hight = min(A[begin], A[highest]);
		//计算中间格子
		int blocks = 0;
		for (i = begin+1; i < highest; i++)
			blocks += min(A[i], hight);
		//计算中间面积
		int area = width*hight;
		area -= blocks;
		//重新定位下一个begin
		begin = highest;
		return area;
	}
};

//2014-1-27 update
	int trap(int A[], int n) 
	{
		int h = 0;
		int sum = 0;

		for (int i = 0, j = n-1; i < j; )
		{
			if (A[i] < A[j])
			{
				h = max(h, A[i]);
				sum += h-A[i];
				i++;
			}
			else
			{
				h = max(h, A[j]);
				sum += h-A[j];
				j--;
			}
		}
		return sum;
	}