#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:高度圖。此題實際上是根據(jù)給定的數(shù)組，畫出高度圖，然后計算出高度圖中可以盛放的雨水。那么關(guān)鍵就是雨水實際的計算過程需要模擬出來。何時會出現(xiàn)雨水？當(dāng)出現(xiàn)至少有連續(xù)三塊bar后，且至少中間的bar高度h2筆兩邊的bar高度h1和h3至少相差>=1,此時構(gòu)成高度差，形成雨水雨水的大小由誰決定?雨水的大小由中間bar的高度h2，左邊連續(xù)bar中出現(xiàn)單調(diào)增的高度h1,與變連續(xù)bar中出現(xiàn)單調(diào)增的高度h3決定，則實際兩側(cè)計算采用的高度h=min(h1, h3)，設(shè)尋找到的從中間bar向左連續(xù)出現(xiàn)單調(diào)增的截止bar橫坐標為x1,                                                            右								 x3則整個盛放雨水的底部寬度w=x3-1-x1，高度h=min(h1,h3)，計算的盛放雨水面積S= 總面積 - 盛放雨水范圍內(nèi)bar面積 = (x3-1-x1) * min(h1, h3) - 對x1到x3-1范圍內(nèi)所有bar面積求和那么問題的關(guān)鍵是如何尋找到作為盛放雨水的左邊的bar和右邊的bar，可以認為左邊到中間bar單調(diào)減，中間bar到右邊單調(diào)增比如1,0,2就是符合上述條件的一種可以這樣，不斷羅列每個數(shù)作為中間底部bar,向左右兩側(cè)伸展，輸入:12(數(shù)組元素個數(shù))0 1 0 2 1 0 1 3 2 1 2 132 0 245 4 1 265 2 1 2 1 5輸出:6(盛放雨水的面積)2114關(guān)鍵:1 正確解法：維護一個左邊的最大高度和右邊的最大高度，如果左邊的最大高度<右邊最大高度，就累加面積=leftMax-A[a]  之所以用最大高度減去bar高度就是水的面積2 漏了小單調(diào)區(qū)間在大單調(diào)區(qū)間中的情況，如5 2 1 2 1 5	//計算左右兩個截止bar中間的bar的總面積	for(int k = left + 1 ; k <= right - 1 ; k++)	{		//易錯，這里bar的高度應(yīng)該為實際高度和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;}