【题目描述】
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/
转载于:https://my.oschina.net/u/3776581/blog/1621700
分享到：
相关推荐
js js_leetcode题解之42-trapping-rain-water.js
c语言入门 C语言_leetcode题解之42-trapping-rain-water.c
在本压缩包中，我们关注的是一个Python编程相关的学习资源，特别针对LeetCode平台上的第42题“接雨水”（Trapping Rain Water）的面试题解。LeetCode是一个广泛被程序员用来提升算法技能和准备面试的在线平台，其中...
Trapping Rain Water 刷题顺序 刷题内容总的来说包括数据结构、算法和技巧 按照tag分类别进行刷题，跳过like<200>like的题目 按Acceptance由高到低进行，每个tag所刷题目大于20(对于类型较少的题目大于5)，则进入下...
Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels...
力码解决方案 Leetcode是一个网站，人们——...├── Trapping Rain Water │ ├── Readme.md │ └── solution.js ├── Wildcard Matching │ ├── Readme.md │ └── solution.js ├── Valid Number │
Trapping Rain Water 85. Maximal Rectangle Monotonic stack for 2d array 239. Sliding Window Maximum 255. Verify Preorder Sequence in Binary Search Tree 907. Sum of Subarray Minimums 二叉搜索树 99. ...
leetcode 不会3D 捕集雨水系统 该 repo 包含复杂 3D 雨水收集系统的解决方案，该系统在 Leetcode Problem ...您必须编写一个函数来计算如果我们将无限供应的水倒在该建筑上时将存储在该建筑中的水量。...
Trapping Rain Water II], BFS/Priority queue 2017.06.19 打卡[LeetCode 145. Binary Tree Postorder Traversal], Tree/stack 2017.06.20 打卡[LeetCode 107. Binary Tree Level Order Traversal II], Tree/BFS ...
多线程 leetcode 前言 每天刷点leetcode，基于java语言实现。 leetcode上难度分三档：easy,medium,hard. 如下： easy medium Remove Nth Node From End of List Swap Nodes ...Trapping Rain Water
Trapping Rain Water Integer to English Words Regular Expression Matching Merge K Sorted Lists Remove Invalid Parentheses Serialize and Deserialize Binary Tree Minimum Window Substring C++ STL中常见...
The transverse trapping forces on a dielectric sphere located at an oil-water interface are theoretically investigated with the ray-optics model. The transverse trapping forces rely on the internal ...
我自己在新学erlang，在LeetCode OJ上找了题目练习，题目很适合新手... "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现erlang的函数式的思维逻辑
二、trapping rain water 雨水收集问题 问题描述 给定一个 number 组成的数组，值代表箱子的高度，下雨后，这些箱子中的间隙一共能收集到多少雨水 解答 暴力破解： 遍历数组，找当前 index 往左的最大值和当前 index...
### 非线性光学效应在利用飞秒脉冲捕获纳米颗粒中的应用 #### 标题解析 本文探讨的主题是“非线性光学效应在利用飞秒脉冲捕获纳米颗粒中的应用”。该研究主要关注如何通过近红外激光的超短脉冲来操纵纳米级别的颗粒...
仿真光纤中孤子捕获的程序.在孤子光通信中有较好的应用价值
接下来，我们转向LeetCode的第42题“接雨水”（Trapping Rain Water）。这是一道典型的二维数组问题，考察的是动态规划和双指针技巧。 题目描述：给定一个高度不一的数组代表地面，雨水会积累在低点。求能容纳的...
接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./Array/rotate-image.md) Heap 堆 [0023 合并K个排序链表](./Heap/merge-k-sorted-lists.md) String 字符串 [0006 Z字形变换](./String/zigzag-...
Adatoms quantum trapping and polarization at Pt and Rh surfaces，孙长庆，，The extremely-high catalytic efficiency of under-coordinated metal adatoms is indeed fascinating but its electronic origin ...