42. 接雨水 [hard]
42. 接雨水 [hard]
https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
通过次数125,762 | 提交次数242,541
Forth Try
2020-07-27
韦恩图面积解法，从矩形之间的交集关系考虑。左边投影和右边投影之和，减去总尺寸，得到的就是包括柱子和积水的面积；再减去柱子面积，得到的就是积水面积。
class Solution:
def trap(self, height: List[int]) -> int:
leftmax, rightmax = 0, 0
leftsum, rightsum = 0, 0
pillar_sum = 0
# 面积的计算，也是化整为零的思路
for i in range(len(height)):
# 统计柱子面积
pillar_sum += height[i]
# 统计从左投影后的面积
leftmax = max(leftmax, height[i])
leftsum += leftmax
# 统计从右投影后的面积
j = len(height) - 1 - i
rightmax = max(rightmax, height[j])
rightsum += rightmax
# 最高柱子撑起的矩形的面积
zone = leftmax * len(height)
# 韦恩图，从矩形之间的交集关系考虑
# 左边投影和右边投影之和，减去总尺寸，得到的就是包括柱子和积水的面积；再减去柱子面积，得到的就是积水面积。
return leftsum + rightsum - zone - pillar_sum
- 执行用时：48 ms, 在所有 Python3 提交中击败了74.63%的用户
- 内存消耗：14.3 MB, 在所有 Python3 提交中击败了8.00%的用户
Third Try
2020-07-27
单调栈解法来一发，在这里终于理解了所谓单调栈的思路。 用在这题的话，还是first try里的想法简单直接。
- 往下走的时候，并不能积累有效的水源，是往栈里放元素的过程。
- 往上走的时候，如果栈里面有元素，就可以考虑一起围起来堆水了。
- 对于栈里面比当前元素小的元素，都需要拉出来处理，不然被当前元素挡住了以后没法发挥作用了。
- 栈中至少要有两个元素才能与当前元素进行比较做水池，栈顶元素被拿出来作为底部，栈顶前一个元素和当前元素拿来做围墙。栈顶元素和当前元素之间可能还有不少距离，但这些距离在栈顶元素高度下的尺寸都在之前被处理过了。这一步想清楚了，才能够理解整个迭代的思路。
- 当只剩一个元素的时候，虽然没法做围墙，但需要考虑是否会被当前元素给踢掉。
class Solution:
def trap(self, height: List[int]) -> int:
col = 0
stack = []
for idx,h in enumerate(height):
# 栈中没有元素作为左边护栏，或者当前元素比stack最小值小，可以提供贡献，就放到stack中去存起来
if not len(stack) or stack[-1][1] >= h: # 等号其实无关紧要，并不影响结果，两个相等的元素之间没法储存水量
stack.append((idx, h))
continue
# 把所有小于当前元素的都去掉，结果其实是形成一个单调递减栈
while len(stack) >= 2 and stack[-1][1] < h:
prev_idx, prev_h = stack.pop()
col += (min(stack[-1][1], h) - prev_h) * (idx - stack[-1][0] - 1) # 距离不能是idx - pre_idx
if stack[-1][1] < h: # 清理最后一个无效元素
stack.pop()
stack.append((idx, h))
return col
- 执行用时：56 ms, 在所有 Python3 提交中击败了38.88%的用户
- 内存消耗：14 MB, 在所有 Python3 提交中击败了8.00%的用户
Second Try
2020-07-27
- 双指针解法，从左求解leftmax, 从右求解rightmax。定义是该元素左边的leftmax和rightmax，不包括该元素。
- 在这个过程中，对于从左到右的元素，该元素左边的leftmax是肯定的，右边的rightmax是不确定的，不过至少大于等于当前的rightmax
- 从右到左的元素，rightmax是肯定的，leftmax是不确定的，确定的是最后的leftmax会大于等于当前的leftmax
- 从左到右的元素，leftmax<rightmax的时候，可以来一发；如果leftmax>rightmax, 没法做决定，那就暂停不走了。这个不走了真是有意思，很难想到。。
- 从右到左的元素，类似。
空间复杂度为O(1)，时间复杂度依然是O(N)，但只扫描一遍。
最特别的地方在于，在双指针同时靠拢的过程中，如果某个指针在某个位置无法做决定，则停下不走，等另一个指针处理靠拢，一下子就把复杂问题解决了。
class Solution:
def trap(self, height: List[int]) -> int:
# 双指针解法，从左求解leftmax, 从右求解rightmax
# 定义是该元素左边的leftmax和rightmax，不包括该元素。
# 在这个过程中，对于从左到右的元素，该元素左边的leftmax是肯定的，右边的rightmax是不确定的，不过至少大于等于当前的rightmax
# 从右到左的元素，rightmax是肯定的，leftmax是不确定的，确定的是最后的leftmax会大于等于当前的leftmax
# 从左到右的元素，leftmax<rightmax的时候，可以来一发；如果leftmax>rightmax, 没法做决定，那就暂停不走了。这个不走了真是有意思，很难想到。。
# 从右到左的元素，类似。
if len(height) < 3:
return 0
leftmax, rightmax = height[0], height[-1]
left, right = 1, len(height) - 2
col = 0
while left <= right:
if leftmax <= rightmax:
col += max(leftmax - height[left], 0)
leftmax = max(leftmax, height[left])
left += 1
# 一般情况下等号两边都可以处理一遍，但每次只处理一边，不然干扰后[2, 0, 2]这种简单案例都会出错
elif rightmax <= leftmax:
col += max(rightmax - height[right], 0)
rightmax = max(rightmax, height[right])
right -= 1
return col
First Try
2020-07-27
比较容易理解的思路，每个元素在其上方能够维持的高度仅由其左右最高高度和当前元素的高度来决定。可以发现这其实是一个化整为零的思路，从考虑整个矩形区间能够储蓄多少水，变成单个x坐标上方能维持多少水。
一个复杂的问题，换了个思路，就变得水到渠成了。
class Solution:
def trap(self, height: List[int]) -> int:
if len(height) < 3:
return 0
left = [0] * len(height) # idx左边的最大值
right = [0] * len(height) # idx右边的最大值
for i in range(len(height)):
j = len(height) - 1 - i
# 考虑的都是前一个的最左最右，和上一个元素的比较，没有当前元素的作用
if i > 0:
left[i] = max(left[i - 1], height[i - 1])
if j < len(height) - 1:
right[j] = max(right[j + 1], height[j + 1])
rv = 0
for i in range(len(height)):
rv += max(min(left[i], right[i]) - height[i], 0)
return rv
- 执行用时：56 ms, 在所有 Python3 提交中击败了38.88%的用户
- 内存消耗：14 MB, 在所有 Python3 提交中击败了8.00%的用户
Failed Try
2020-07-25
思路没理清楚，写了一堆还是错了。
class Solution:
def trap(self, height: List[int]) -> int:
if len(height) <= 1:
return 0
prev = [(0, height[0])]
rv = 0
drops = []
for i in range(1, len(height)):
if height[i] == 0:
continue
if height[i] < height[i - 1]:
prev.append((i, height[i]))
elif height[i] == height[i - 1]: # 每次遇到新元素，不管如何都会被添加进去，因此遇到相等的，只要去除上一个元素就行
prev.pop()
else:
# 需要考虑为0 或者没有prev存在的情况
if len(prev) == 0:
prev = [(i, height[i])]
continue
nprev = []
drop = 0
h, gap = min(prev[0][1], height[i]), i - prev[0][0]
if prev[0][1] > h:
nprev.append(prev[0]) # 左边界依然是最大元素，仍然有效
rv -= drops[-1] # 还是在之前的圈子里兜兜转转，需要减去一波再重来
# 其实本质上是左右两个有效的边界挖了一个水池，中间的元素都是用来填充土方的，最后看剩下的水空间有多少啊
# 中间元素用来填充的思路一旦发现，事情就变得很简单了，处理过程中也只需要维护最高元素和其右边的元素就行了
drop += h * gap
for i in range(1, len(prev)):
drop -= prev[i][1]
if prev[i][1] > height[i]:
nprev.append(prev[i])
nprev.append((i, height[i]))
prev = nprev
drops.append(drop)
rv += drop
print("idx", i, "available prev", prev, "result", rv)
return rv