哈喽各位大佬好，我是菜鸟小明哥。扯个闲篇，姚期智大佬原本是学物理的，哈佛物理学博士，何凯明原本也是学过物理的，张朝阳也是学物理的（还是清华的物理），而本菜鸟也是学物理的，哈哈，说明我也有变成大佬的潜质。

 接雨水1，力扣官方：实心柱体中间能存多少雨水？（柱体不一样高，因而能存水）

采用dp法来做，从左边来看柱体的最值，存储一个数组，从右边来看柱体的最值，存储一个数组，然后取两者的最小值，得到最终的结果

状态转移关系：

class Solution:def trap(self, height: List[int]) -> int:ans=0if not height:return 0n = len(height)leftMax = [height[0]] + [0] * (n - 1)for i in range(1, n):leftMax[i] = max(leftMax[i - 1], height[i])rightMax = [0] * (n - 1) + [height[n - 1]]for i in range(n - 2, -1, -1):rightMax[i] = max(rightMax[i + 1], height[i])for i in range(n):ans += min(leftMax[i], rightMax[i]) - height[i]return ans

 接雨水2，这个难度很大，将上面的换成了立体的，需要用到队列，忽略吧，谁要考这个直接说不会吧。故而，接雨水换成另一题：力扣官方：每个房屋至少有一个接雨水的桶，需要多少个桶？

题先读懂哈，如下举例：H代表房屋，符号.（英文句号）代表空位置

每个H至少有一个桶来接雨水（可以共用一个桶，例如"H.H",只需一个桶即满足题意），而且要有空位置放桶接雨水，没有空位置则无法满足，比如字符串"HH"（没有空位置），".HHH."(中间的房屋H无法放桶接雨水，因为它旁边也没有空位置) 这些情况返回-1，没有房屋H的情况就不需要桶来接雨水了，这种返回0，例如"......",".."

class Solution:def minimumBuckets(self, street: str) -> int:n = len(street)i = ans = 0while i < n:if street[i] == "H":if i + 1 < n and street[i + 1] == ".":ans += 1# 直接跳过后续的两个位置i += 2elif i - 1 >= 0 and street[i - 1] == ".":ans += 1else:return -1i += 1return ans

直接做就是了，找房H，然后找两边的空位置，有就放桶。注释表示：如果是H.H或者H..就不需要考虑了直接跳过即可，就放一个桶就行。

愿我们终有重逢之时，

而你还记得我们曾经讨论的话题。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！