题目描述
给定n个非负整数，代表着一个高度柱状图连续n个图的高度。本题需要计算这个柱状图能够蓄水的数量。
解题思路
蓄水的情况主要如下图：
假设heights代表所有的柱状图高度， heights[i](0<=i<len(heights))代表第i个柱状图的高度：
根据上图一、图二和图三可知：
- 当任意
heights数值呈单调的时候，不存在蓄水量。 - 当
heights仅存在类正态曲线的分布时，不存在蓄水量。
笔者先将情况缩小为len(heights) == 3，结合图四可知：
- 当
heights[i] < heights[i+1] and heights[i] < heights[i-1]时存在蓄水量。 - 当前可以蓄水，蓄水量为
(min(heights[i], heights[i-1]) - heights[i]) - 此时相当于
heights[i] = min(heights[i], heights[i-1])
接下将场景扩大下len(heights) > 3，可参见图五和图六：
假设当前的bar的下标为k，检查蓄水的bar下标为i(i<k)，此时任意j(i<j<k)都有heights[i] < heights[j] < heights[j+1] < heights[k]：
- 当
heights[i-1] > heights[i]时存在蓄水量，执行2，否则执行5。 - 蓄水量相当于
(min(min(heights[i+1:k+1]), heights[i-1]) - heights[i]) * (k-i)。 - 此时相当于
heights[i] = min(min(heights[i+1:k+1]), heights[i-1])。 -
i=i-1，执行步骤1。 -
k=k+1,i=k-1执行步骤1。
根据上述步骤可以一步步获得最终的结果，得算法如下：
class Solution:
def trap(self, height: List[int]) -> int:
water = 0
hi = 2
while hi < len(height):
if height[hi] < height[hi-1]:
hi+=1
continue
bar = self._get_last_bar(height, hi-1, height[hi])
while bar is not None:
for i in range(hi-1, bar-1, -1):
water += min(height[hi], height[bar-1]) - height[i]
height[i] = min(height[hi], height[bar-1])
bar = self._get_last_bar(height, bar-1, height[hi])
hi+=1
return water
def _get_last_bar(self, height, lo, mh):
if lo - 1 < 0:
return None
while lo - 1 >= 0 :
if height[lo] < min(height[lo-1], mh):
return lo
lo-=1
return None
上述算法实际上是O(n^2)，算法还存在比较多得优化空间：
- 如使用栈来减少回朔(
O(n))：https://leetcode.com/problems/trapping-rain-water/discuss/17414/A-stack-based-solution-for-reference-inspired-by-Histogram - 使用双指针遍历法(
O(n))：https://leetcode.com/problems/trapping-rain-water/discuss/17554/Share-my-one-pass-Python-solution-with-explaination
相关题目：