从来好事天生俭,自古瓜儿苦后甜。这篇文章主要讲述Lintcode363 Trapping Rain Water solution 题解相关的知识,希望能为你提供帮助。
【题目描述】
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.
文章图片
给定n个非负整数,表示一个高程图,其中每个条形图的宽度为1,计算下雨后它能捕到多少水。
文章图片
【题目链接】
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 题解】
推荐阅读
- Unity打包android时会出的一些问题
- Qt for Android 启动短暂的黑屏或白屏问题如何解决()
- Spring使用MappingJackson2MessageConverter发送接收ActiveMQ消息
- pycharm运行Django发生AppRegistryNotReady: Apps aren't loaded yet.
- Lintcode364 Trapping Rain Water II solution 题解
- Android TextView数字增长动画效果
- 安卓的权限大全和动态使用安卓权限
- android——No matching client found for package错误处理
- android——Installation error: INSTALL_FAILED_CONFLICTING_PROVIDER 解决方案