国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

leecode 解題總結:42. Trapping Rain Water

2019-11-10 17:34:39
字體:
來源:轉載
供稿:網友
#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;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 外汇| 井冈山市| 漾濞| 霍州市| 内乡县| 福泉市| 迁西县| 平阴县| 上饶市| 浦县| 江津市| 阳朔县| 宣武区| 虎林市| 那曲县| 和龙市| 金溪县| 宜兰县| 邢台县| 麻江县| 商丘市| 陕西省| 勃利县| 宁乡县| 新竹市| 樟树市| 来凤县| 中山市| 千阳县| 贺州市| 九寨沟县| 将乐县| 呼伦贝尔市| 泰州市| 辽宁省| 永平县| 宿州市| 苏州市| 岱山县| 长葛市| 清河县|