程序员人生 网站导航

leetcode No42. Trapping Rain Water

栏目:php教程时间:2016-11-28 13:31:15

Question:

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!

数组元素代表高度,如图所示,求能装多少水

Algorithm:

分别从左右两边向最高点逼近,只在元素小的1边地方储水。由左侧向最高点逼近时,设左侧当前的最大值leftmax,当前遍历到i,如果leftmax > A[i]; sum += (leftmax- A[i]);否则,currentMax = i,此条带没法储水;由右侧逼近最高点类似左侧。

Accepted Code:
class Solution { public: int trap(vector<int>& height) { int left=0; int right=height.size()⑴; int leftmax=0; //左侧最大值 int rightmax=0; //右侧最大值 int res=0; //结果 while(left<=right) { if(height[left]<=height[right]) { if(height[left]>leftmax) leftmax=height[left]; else res+=leftmax-height[left]; left++; } else { if(height[right]>rightmax) rightmax=height[right]; else res+=rightmax-height[right]; right--; } } return res; } };



------分隔线----------------------------
------分隔线----------------------------

最新技术推荐