[toc]
- 标签：栈、数组、双指针、动态规划、单调栈
- 难度：困难
描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，用数组 height 表示，其中 height[i] 表示第 i 根柱子的高度。
要求：计算按此排列的柱子，下雨之后能接多少雨水。
说明：
-
$n == height.length$ 。 -
$1 \le n \le 2 * 10^4$ 。 -
$0 \le height[i] \le 10^5$ 。
示例：
- 示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 - 示例 2：
输入：height = [4,2,0,3,2,5]
输出：9- 遍历高度数组
height。 - 如果当前柱体高度较小，小于等于栈顶柱体的高度，则将当前柱子高度入栈。
- 如果当前柱体高度较大，大于栈顶柱体的高度，则一直出栈，直到当前柱体小于等于栈顶柱体的高度。
- 假设当前柱体为
C，出栈柱体为B，出栈之后新的栈顶柱体为A。则说明：- 当前柱体
C是出栈柱体B向右找到的第一个大于当前柱体高度的柱体，那么以出栈柱体B为中心，可以向右将宽度扩展到当前柱体C。 - 新的栈顶柱体
A是出栈柱体B向左找到的第一个大于当前柱体高度的柱体，那么以出栈柱体B为中心，可以向左将宽度扩展到当前柱体A。
- 当前柱体
- 出栈后，以新的栈顶柱体
A为左边界，以当前柱体C为右边界，以左右边界与出栈柱体B的高度差为深度，计算可以接到雨水的面积。然后记录并更新累积面积。
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
stack = []
size = len(height)
for i in range(size):
while stack and height[i] > height[stack[-1]]:
cur = stack.pop(-1)
if stack:
left = stack[-1] + 1
right = i - 1
high = min(height[i], height[stack[-1]]) - height[cur]
ans += high * (right - left + 1)
else:
break
stack.append(i)
return ans-
时间复杂度：$O(n)$，其中
$n$ 是数组height的长度。 - 空间复杂度：$O(n)$。
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
s1, s2 = 0, 0
max1, max2 = 0, 0 # 思考max1和max2的作用，是通过什么方式进行迭代的；【maxn其实代表的是当前最高的柱子】【s1和s2都是在外层循环中靠一根一根柱子累加起来的】
for i in range(n):
# 这里写的是一个循环里边套两个判断，而不是了两个循环
if height[i] > max1:
max1 = height[i] # 如果现在柱子的高度（所占的面积）大于max1则进行赋值
if height[n - 1 - i] > max2:
max2 =height[n - 1 - i]
s1 += max1
s2 += max2
res = s1 + s2 - n *max(height) -sum(height)
return res 