用单调栈实现算法题接雨水

题目描述：

给定n个非负整数表示每个宽度为1的柱子的高度图，计算下雨后能够捕获的雨水量。

示例：

输入：[0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：如图所示，这是雨水的容器。

思路：

1. 定义一个栈stack，用来存储柱子的下标。定义一个变量ans，用来存储接到的雨水量。定义一个变量cur，用来存储当前的下标。

2. 遍历数组，如果stack为空或者当前柱子高度小于等于栈顶柱子高度，把当前下标入栈。

3. 如果当前柱子高度大于栈顶柱子高度，说明形成了一个凹槽，可以接到雨水。此时需要弹出栈顶元素，计算当前柱子和新的栈顶柱子之间的距离和高度差，用来计算接到的雨水量。

4. 如果当前柱子高度大于栈顶柱子高度，重复第3步，直到当前柱子高度小于等于栈顶柱子高度或者栈为空。

5. 遍历结束后，栈中剩余的柱子没有形成凹槽，无法接到雨水，将栈中剩余的柱子依次出栈，计算接到的雨水量。

代码实现：

C++实现：

class Solution {
public:
int trap(vector<int>& height) {
stack<int> s;
int ans = 0;
for (int i = 0; i < height.size(); i++) {
while (!s.empty() && height[i] > height[s.top()]) {
int cur = s.top();
s.pop();
if (s.empty()) break;
int left = s.top();
int right = i;
int h = min(height[left], height[right]) - height[cur];
ans += h * (right - left - 1);
}
s.push(i);
}
return ans;
}
};

Python实现：

class Solution:
def trap(self, height: List[int]) -> int:
s = []
ans = 0
for i in range(len(height)):
while s and height[i] > height[s[-1]]:
cur = s[-1]
s.pop()
if not s: break
left = s[-1]
right = i
h = min(height[left], height[right]) - height[cur]
ans += h * (right - left - 1)
s.append(i)
return ans