您当前位置：首页 > php开源 > php教程 > leetcode No42. Trapping Rain Water

leetcode No42. Trapping Rain Water

来源：程序员人生发布时间：2016-11-28 13:31:15 阅读次数：2698次

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; } };

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

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

上一篇 市政智能化管理系统开发

下一篇 浅谈主流热修复技术

分享到:

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

为码而活

积分：4237

15粉丝

7关注

栏目热点