题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 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

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

解决方案：

这段代码是基于单调栈求解 “接雨水” 问题的经典实现，核心思路是利用单调递减栈记录柱子下标，遍历过程中通过弹出栈顶元素确定 “低洼处”，结合左右两侧的更高柱子计算该位置能承接的雨水量，最终累加得到总雨水量。

核心逻辑

1. 核心定义：

   • ans：总接雨水量，初始值为 0；
   • num：单调栈（存储柱子下标），栈内下标对应的柱子高度严格单调递减，用于记录 “左侧更高柱子” 的候选位置。

2. 遍历方式：从左到右遍历柱子数组，逐个处理每个位置的柱子，利用栈的单调性找到能形成 “接水区域” 的左右边界。

3. 单调栈核心操作（核心是找 “低洼 + 左右边界”）：

   • 对于当前下标i的柱子高度tmp_h：① 触发接水条件：循环检查栈顶元素，若当前柱子高度≥栈顶下标对应的高度，说明栈顶位置是 “低洼处”，开始计算接水量；② 计算单块接水量：
     • 弹出栈顶下标作为 “低洼处”，记录其高度cur_h；
     • 若栈空则无左侧边界，终止当前循环；
     • 取新的栈顶下标作为 “左边界”，当前下标i作为 “右边界”；
     • 接水高度 = 左右边界的较小高度 - 低洼处高度（min(height[left_num], tmp_h) - cur_h）；
     • 接水宽度 = 右边界下标 - 左边界下标 - 1；
     • 单块接水量 = 接水高度 × 接水宽度，累加到总水量ans；③ 入栈当前下标：将i压入栈，维持栈的单调递减特性。

4. 结果返回：遍历完成后，ans即为整个数组能承接的总雨水量，直接返回。

关键特点

• 时间复杂度 O (n)：每个柱子仅入栈、出栈各一次，无嵌套循环的额外开销；
• 空间复杂度 O (n)：栈最多存储所有柱子下标（最坏情况高度单调递减）；
• 单调栈特性：栈内下标对应的高度始终单调递减，确保能快速定位 “低洼处” 的左右更高边界；
• 逻辑直观：将接雨水问题拆解为 “多个独立的接水区域”，逐个计算累加，符合 “低洼存水” 的物理直觉。

验证示例（以height = [0,1,0,2,1,0,1,3,2,1,2,1]为例）

• 遍历到 i=3（高度 2）：栈顶 i=2（高度 0）、i=1（高度 1）依次弹出，计算 i=2 处接水量 1×1=1，i=1 处接水量 1×1=1，总 ans=2；
• 遍历到 i=7（高度 3）：依次弹出栈内低高度柱子，计算多个接水区域的水量，最终总 ans=6（与预期结果一致）。

总结

1. 核心思路：利用单调递减栈定位 “低洼处” 和其左右更高边界，将接雨水问题拆解为多个小区域的水量计算，累加得到总量；
2. 关键设计：栈存储下标而非高度值，既保留高度对比能力，又能直接计算接水宽度；
3. 功能效果：是 “接雨水” 问题的最优解法之一，能高效处理任意长度的柱子数组，结果精准。

函数源码：

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        int ans=0;
        stack<int> num={}; //下标
        for(int i=0;i<len;i++){
            int tmp_h=height[i];
            while(!num.empty() && tmp_h>=height[num.top()]){
                int cur_h = height[num.top()];//拿出栈顶--当前遍历的高度
                num.pop();
                if(num.empty()) break;
                int left_num =num.top(); 
                int s_h=min(height[left_num],tmp_h)-cur_h;
                int s=s_h*(i-left_num-1);

                ans+=s;
            }
            num.push(i);
        }
        return ans;
    }
};