"""
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
"""
import inspect
'''
出于加解法考虑，这题貌似动态规划比较好。
出于简单考虑，可以分列求，暴力解法，见Solution
但是出于栈专题考虑，还是在Solution1里面使用栈解。
'''
# ------------------------------------------------------------------------------------
# 分列求
# 第一列和最
题目 "leetcode42 接雨水" 是一个经典的计算机算法问题，目标是计算在给定的一组柱状图中，能够接住多少雨水。柱子的宽度为 1，高度不等，雨水会在柱子间积累。给定一个非负整数数组 `height`，代表每个柱子的高度，我们需要计算出在下雨后，柱子之间能接住的雨水总量。
### 解决方案
#### 分列求（暴力解法）
这种方法是从每列开始分别计算能接住的雨水。对于每一列，我们需要找到左边的最大高度和右边的最大高度。如果当前柱子的高度小于左右两边的最大高度中的较小值，那么它就能接住 `(min(left_max, right_max) - height[i])` 单位的雨水。遍历整个数组，累加所有柱子能接住的雨水即可得到总雨水量。注意第一列和最后一列只需要考虑一个方向的最大高度。
```python
class Solution:
def trap(self, height):
if len(height) <= 1:
return 0
left_max = height[0]
right_max = max(height[i + 1:] for i in range(len(height) - 1))
ans = 0
for i in range(1, len(height) - 1):
left_max = max(height[i - 1], left_max)
right_max = max(height[i + 1], right_max)
ans += min(left_max, right_max) - height[i]
return ans
```
#### 栈法（高效解法）
栈法是一种更高效的空间优化解决方案。我们使用一个栈来保存柱子的索引，栈顶的元素总是当前已遍历到的柱子中最高的。遍历数组，当遇到比栈顶元素高的柱子时，说明栈顶的柱子被当前柱子和栈中更早的柱子界定，可以开始计算雨水。将栈顶元素弹出，并累加到答案 `ans`，直到栈为空。如果当前柱子的高度小于或等于栈顶元素，将当前柱子的索引入栈。这个过程持续到数组遍历完。
```python
class Stack:
def __init__(self):
self.stack = []
def push(self, x):
self.stack.append(x)
def pop(self):
if self.stack:
return self.stack.pop()
else:
return 0
def top(self):
if self.stack:
return self.stack[-1]
else:
return 0
def isEmpty(self):
return len(self.stack) == 0
class Solution1:
def trap(self, height):
ans = 0
current = 0
st = Stack()
while current < len(height):
if height[current] <= st.top():
top = st.top()
st.pop()
while not st.isEmpty() and height[current] > height[st.top()]:
top = st.top()
st.pop()
distance = current - st.top() - 1
bounded_height = min(height[current], height[st.top()]) - height[top]
ans += distance * bounded_height
st.push(current)
current += 1
return ans
```
### 总结
本题考察了两种不同的算法思路：暴力分列法和栈法。暴力分列法虽然直观，但时间复杂度较高，不适合大数据量的情况。栈法则通过优化空间复杂度，提高了效率，是解决此类问题的常见方法。理解这两种方法的原理和实现，有助于提高在实际编程问题中解决问题的能力。
