🔗 接雨水

题目来源：42. 接雨水 – 力扣（LeetCode）

---

📌 题目描述

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

每个柱子的宽度为 1，高度由数组 height 给出。

返回可以接住的雨水的总量（单位：面积）。

---

✅ 示例解析

示例 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
• 解释：从索引 2 到 4 的低洼区域被两侧高柱包围，可积水 9 单位。

---

⚠️ 提示

• n == height.length
• 1 <= n <= 2 × 10⁴
• 0 <= height[i] <= 10⁵

---

💡 解法：单调栈（Monotonic Stack）—— O(n) 时间，O(n) 空间

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int ans = 0;

        for (int i = 0; i < height.length; i++) {
          
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int bottom = stack.pop(); 

                if (stack.isEmpty()) {
                    break; 
                }

                int left = stack.peek(); 
                int waterHeight = Math.min(height[left], height[i]) - height[bottom];
                int width = i - left - 1; 

                ans += waterHeight * width; 
            }
            stack.push(i); 
        }

        return ans;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  每个索引最多入栈和出栈一次，整体遍历为线性时间。
• 空间复杂度：O(n)
  栈的空间最多存储 n 个索引，在最坏情况下（递减序列）达到 O(n)。

---

🧩 解题思路

1. 核心思想：凹槽积水
   雨水只能在“凹”形区域中积聚，即存在左右两个“高点”，中间较低。
   每当出现一个右侧更高柱子时，就可能与前面的凹槽形成“容器”来接水。
2. 单调栈的作用：
   • 维护一个单调递减的柱子高度索引栈。
   • 当遇到一个更高的柱子（height[i] > height[stack.peek()]）时，说明可能形成了一个右边界，可以开始计算积水。
3. 计算积水面积：
   • bottom：弹出的栈顶，是凹槽底部（最低点）
   • left：新的栈顶，是左边界
   • i：当前索引，是右边界
   • 水面高度：min(height[left], height[i])
   • 实际积水高度：水面高度 - bottom高度
   • 宽度：i - left - 1
   • 面积：高度 × 宽度
4. 为什么是单调递减？
   只有当柱子高度下降时，才可能形成凹槽。一旦上升，就尝试“填补”前面的凹陷区域。
5. 举例说明：
   对于 [0,1,0,2,...]：
   • 当 i=3（高度 2）到来时，发现它比 stack.peek()（索引 2，高度 0）高，开始出栈。
   • 弹出 2（高度 0），左边界是 1（高度 1），水面高度为 min(1,2)=1，积水高度 1-0=1，宽度 3-1-1=1，面积 1。
   • 继续判断是否比新的栈顶高，直到栈恢复单调性。