Leetcode#42 Trapping Rain Water

type
status
date
slug
summary
tags
category
icon
password
如图所示，蓝色区域就是☔️积水区，现在需要计算这个值。
notion image

思路

以最高的柱子P为终点，从左L向P移动。
  • 如果L右边的柱子L2的长度低于当前L的高度，那么在该柱子上可以累积array[L]-array[L2]的雨水量
  • 如果L右边的柱子L2的长度大于等于当前L的高度，那么，L-L2实际上已经形成了一个池塘了
  • 从L2开始往右寻找池塘，直至找到P
找到P之后，就不能这样找了，因为右边不存在可以与P形成池塘的柱子。所以，从最右边往左找，思路和上面一致。

代码

Loading...

© XGFan 2012-2025