42.接雨水

题目

给定 n 个非负整数表示每个宽度为 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

题解

class Solution {
    public int trap(int[] height) {
// 核心思路：双指针 + 贪心（利用木桶效应/短板原理）
    // 1. 基本原理：
    //    某个位置 i 能接的水量 = min(左边最高墙, 右边最高墙) - height[i]。
    //    也就是说，水位高度由两边“较矮”的那堵墙决定。

    // 2. 为什么比较 lMax 和 rMax？
    //    我们维护 lMax（左边当前最高）和 rMax（右边当前最高）。
    //    - 如果 lMax < rMax：
    //      说明对于当前 left 指针所在位置，其【左边界上限】由于比【右边某个已知的墙 rMax】矮，
    //      所以水位的瓶颈一定在左边（lMax）。即使 left 和 right 中间有比 rMax 更高的墙，
    //      由于 lMax 已经是短板，水位也被限制在 lMax。
    //      因此可以直接计算 left 处的积水，并向右移动 left。

    //    - 如果 lMax >= rMax：
    //      同理，说明右边是短板，瓶颈在 rMax。
    //      因此可以直接计算 right 处的积水，并向左移动 right。

    // 3. 空间优化：
    //    相比于动态规划（需要两个数组存储所有位置的左右最高墙），
    //    双指针做法只需要 O(1) 的空间。
        int left = 1,right = height.length - 2;
        int lMax = height[0],rMax = height[height.length - 1];
        int totalWater = 0;
        while(left<=right){
            if(lMax < rMax){
                totalWater += Math.max(0,lMax-height[left]);
                lMax = Math.max(lMax,height[left++]);
            }
            else{
                totalWater += Math.max(0,rMax-height[right]);
                rMax = Math.max(rMax,height[right--]);
            }
        }

        return totalWater;

        // //解法1：核心思路：
        // //一个地方能放下的水 = min（左边最高的柱面，右边最高的柱面）-自身高度。
        // int n = height.length;
        // //左右两边最高的柱面记录
        // int[] leftMax = new int[n];
        // int[] rightMax = new int[n];
        // int max = 0;
        // for(int i=0;i<n;i++){
        //     leftMax[i] = max;
        //     if(max<height[i]) max = height[i];
        // }

        // max = 0;
        // for(int i = n-1;i>=0;i--){
        //     rightMax[i] = max;
        //     if(height[i]>max) max = height[i];
        // }

        // int totalWater = 0;
        // //计算当前位置能放下的水
        // for(int i = 0;i<n;i++){
        //     int currentWater = Math.min(leftMax[i],rightMax[i]) - height[i];
        //     if(currentWater>0){
        //         totalWater+=currentWater;
        //     }
        // }

        // return totalWater;

    }
}