问题分析

从左往右遍历数组height，对于每个元素执行如下的单调栈操作：

若栈不为空，且栈顶元素的高度值小于当前元素的高度值，说明栈顶元素可以接雨水。

• 弹出栈顶元素，记为floor，表示当前接雨水区域底部的高度
• 若此时栈为空，说明左边没有墙体，无法接雨水，跳出循环。
• 否则，再取一个栈顶元素left，获取左墙的高度和下标
• 根据已知信息，便可以获取以floor为底，以left作为左墙体，以当前元素为右墙体，构成区域所能截取的雨水量

上述流程执行完成后，此时栈顶元素的高度大于等于当前元素的高度，当前元素是潜在的左墙体，因此压入单调栈中。

程序代码

C++

class Solution {
public:int trap(vector<int>& height) {// 存储下标stack<int> stk;int res = 0;for(int i = 0; i < height.size(); i++) {while( !stk.empty() && height[stk.top()] < height[i] ) {int floor = stk.top();stk.pop();// 边界情况：没有左墙if( stk.empty() )  break;// 获取左墙高度int left = stk.top();int curHeight = min(height[left],  height[i]) - height[floor];res += curHeight * (i - left - 1);}stk.push(i);}return res;}
};

Go

func trap(height []int) int {stack := []int{}res := 0for i, h := range height {for len(stack) > 0 && height[stack[len(stack)-1]] < h {floor := stack[len(stack) - 1]stack = stack[:len(stack) - 1]if len(stack) == 0 {break;}left := stack[len(stack) - 1]curHeight := min(height[left], h) - height[floor]res += curHeight * (i - left - 1)}stack = append(stack, i)}return res
}func min(a, b int) int {if a <= b {return a}return b
}