Lintcode363 Trapping Rain Water solution 题解

从来好事天生俭,自古瓜儿苦后甜。这篇文章主要讲述Lintcode363 Trapping Rain Water solution 题解相关的知识,希望能为你提供帮助。
【题目描述】 
Given  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.
 
 

Lintcode363 Trapping Rain Water solution 题解

文章图片
  给定n个非负整数,表示一个高程图,其中每个条形图的宽度为1,计算下雨后它能捕到多少水。
 
 
Lintcode363 Trapping Rain Water solution 题解

文章图片
  【题目链接】
www.lintcode.com/en/problem/trapping-rain-water/
【题目解析】
此题挨个分析每个A[i]能trapped water的容量,然后将所有的A[i]的trapped water容量相加即可
其次,对于每个A[i]能trapped water的容量,取决于A[i]左右两边的高度(可延展)较小值与A[i]的差值,即volume[i] = [min(left[i], right[i]) - A[i]] * 1,这里的1是宽度,如果the width of each bar is 2,那就要乘以2了”
那么如何求A[i]的左右高度呢? 要知道,能盛多少水主要看短板。那么对每个A[i]来说,要求一个最高的左短板,再求一个最高的右短板,这两个直接最短的板子减去A[i]原有的值就是能成多少水了。
所以需要两遍遍历,一个从左到右,找最高的左短板;一个从右到左,找最高的右短板。最后记录下盛水量的总值就是最终结果了。
【参考答案】
www.jiuzhang.com/solutions/trapping-rain-water/
【Lintcode363 Trapping Rain Water solution 题解】

 



    推荐阅读