leecode 解题总结：42. Trapping Rain Water

#include <iostream>#include <stdio.h>#include <vector>using namespace std;/*问题: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!分析:elevation map:高度图。此题实际上是根据给定的数组，画出高度图，然后计算出高度图中可以盛放的雨水。那么关键就是雨水实际的计算过程需要模拟出来。何时会出现雨水？当出现至少有连续三块bar后，且至少中间的bar高度h2笔两边的bar高度h1和h3至少相差>=1,此时构成高度差，形成雨水雨水的大小由谁决定?雨水的大小由中间bar的高度h2，左边连续bar中出现单调增的高度h1,与变连续bar中出现单调增的高度h3决定，则实际两侧计算采用的高度h=min(h1, h3)，设寻找到的从中间bar向左连续出现单调增的截止bar横坐标为x1,                                                            右								 x3则整个盛放雨水的底部宽度w=x3-1-x1，高度h=min(h1,h3)，计算的盛放雨水面积S= 总面积 - 盛放雨水范围内bar面积 = (x3-1-x1) * min(h1, h3) - 对x1到x3-1范围内所有bar面积求和那么问题的关键是如何寻找到作为盛放雨水的左边的bar和右边的bar，可以认为左边到中间bar单调减，中间bar到右边单调增比如1,0,2就是符合上述条件的一种可以这样，不断罗列每个数作为中间底部bar,向左右两侧伸展，输入:12(数组元素个数)0 1 0 2 1 0 1 3 2 1 2 132 0 245 4 1 265 2 1 2 1 5输出:6(盛放雨水的面积)2114关键:1 正确解法：维护一个左边的最大高度和右边的最大高度，如果左边的最大高度<右边最大高度，就累加面积=leftMax-A[a]  之所以用最大高度减去bar高度就是水的面积2 漏了小单调区间在大单调区间中的情况，如5 2 1 2 1 5	//计算左右两个截止bar中间的bar的总面积	for(int k = left + 1 ; k <= right - 1 ; k++)	{		//易错，这里bar的高度应该为实际高度和realHeight的较小值，否则会多减		barArea += min( height.at(k) , realHeight);	}*/class Solution {public:    int trap(vector<int>& height) {        if(height.empty())		{			return 0;		}		int size = height.size();		int leftMax = INT_MIN;		int rightMax = INT_MIN;		int low = 0 ; 		int high = size - 1;		int water = 0;		while(low <= high)		{			leftMax = max(leftMax , height.at(low));			rightMax = max(rightMax , height.at(high));			//如果左边小于右边，则左边可以存储水			if(leftMax < rightMax)			{				water += (leftMax - height.at(low));				low++;			}			else			{				water += (rightMax - height.at(high));				high--;			}		}		return water;    }};void process(){	int num;	int value;	vector<int> height;	Solution solution;	while(cin >> num)	{		height.clear();		for(int i = 0 ; i < num ; i++)		{			cin >> value;			height.push_back(value);		}		int result = solution.trap(height);		cout << result << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}