Leetcode#42 Trapping Rain Water
type
Post
status
Published
date
Oct 22, 2020
slug
summary
tags
hard
category
Leetcode
icon
password
如图所示，蓝色区域就是☔️积水区，现在需要计算这个值。
思路
以最高的柱子P为终点，从左L向P移动。
- 如果L右边的柱子L2的长度低于当前L的高度，那么在该柱子上可以累积array[L]-array[L2]的雨水量
- 如果L右边的柱子L2的长度大于等于当前L的高度，那么，L-L2实际上已经形成了一个池塘了
- 从L2开始往右寻找池塘，直至找到P
找到P之后，就不能这样找了，因为右边不存在可以与P形成池塘的柱子。所以，从最右边往左找，思路和上面一致。
代码
Loading...