模拟法

最简单的方式，模拟，如果面试遇到原题完全可以使用这种方法，leetcode只有4个用例过不了。

模拟的求水方式是一层一层求，遍历每个位置，如果当前的高度小于 i，并且两边有高度大于等于 i 的，说明这个地方一定有水，水就可以加1。

如果求高度为 i 的水，首先用一个变量 temp 保存当前累积的水，初始化为0。从左到右遍历墙的高度，遇到高度低于i的，说明可以存水，遇到高度大于等于 i 的时候，就需要把记录的temp加到总和sum中，并重置temp，表示这一个小凹槽的水更新完毕了。然后继续循环。时间复杂度为O(n*m)。

代码的关键就是 isStart; 用它可以巧妙处理height[0]为0的影响，只有第一次遇到height[j]大于高度i的情况，才能将isStart置为true 开始用temp记录积累的水量。

class Solution {
public int trap(int[] height) {
    int sum = 0;
    int max = getMax(height);//找到最大的高度，以便遍历。
    for (int i = 1; i <= max; i++) { // 从第i层开始遍历
        boolean isStart = false; //标记是否能够开始更新 temp
        int temp_sum = 0;
        for (int j = 0; j < height.length; j++) {
            if (isStart && height[j] < i) {
                temp_sum++;
            }
            if (height[j] >= i) {
                // 第一次遇到>=i的区块时 就将isStart置true 表示墙壁封闭了 temp从此开始可以更新了
                isStart = true;
                sum += temp_sum;
                temp_sum = 0;  // 封闭了 需要将temp_sum置为0 重新开始计数
            }
        }
    }
    return sum;
}
private int getMax(int[] height) {
		int max = 0;
		for (int i = 0; i < height.length; i++) {
			if (height[i] > max) {
				max = height[i];
			}
		}
		return max;
}

}

最直接且简单的方式

参考自力扣题解：https://leetcode.cn/problems/trapping-rain-water/solutions/3732547/shuang-onfu-za-du-wu-xu-shuang-zhi-zhen-hkrbi，是最清晰且最简单的做法。
视频解析：【毒瘤面试题：接雨水】 https://www.bilibili.com/video/BV1TSPeeGEHC/?share_source=copy_web&vd_source=678f52c7135e8109c9d58a20f6e13fbc

有点类似前缀和算法。

对于每个位置i（不包含最左和最右），该位置能接住的雨水量取决于其左侧最高柱子和右侧最高柱子中的较小值，减去当前位置的高度。 即：雨水量=min(左侧最高,右侧最高)−当前高度。
只需要维护两个数组，分别存对于位置i左侧最高的和右侧最高的值即可。

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if(len <= 2) return 0;

        int[] leftH = new int[len];
        int[] rightH = new int[len];

        // 需要初始化
        leftH[0] = height[0]; 
        rightH[len-1] = height[len-1];

        for(int i = 1; i < len; i++){
            leftH[i] = Math.max(leftH[i-1], height[i]); //左边的最大值
        }
        for(int i = len - 2; i >= 0; i--){
            rightH[i] = Math.max(rightH[i+1], height[i]);  //求出右边的最大值
        }
        int sum = 0;
        for(int i = 1; i < len -1; i++){
            // 每一列的雨水数 = max(0, 左右侧的最小高度-自己的高度)
            sum += Math.max(0, Math.min(leftH[i], rightH[i]) -height[i]);
        }
        return sum;
    }
}

双指针方法

感觉像是上一中算法的改进版本，复杂度可以到0n级别。一遍遍历，用两个变量维护当前位置的左侧最大值和右侧最大值。

left指针与right指针，分别关注左侧区域与右侧区域。
例如，如果 leftMax < rightMax，说明：

• 左边的最大高度是限制因素（短板在左边）
• 右边已经有足够高的”墙”来拦住水
• 所以可以安全地计算​​左边​​当前位置的积水量

反之亦然：如果 rightMax <= leftMax，说明右边的最大高度是限制因素，可以安全计算​​右边​​的积水量。

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int preMax = 0; // 前缀最大值，随着左指针 left 的移动而更新
        int sufMax = 0; // 后缀最大值，随着右指针 right 的移动而更新
        int left = 0;
        int right = height.length - 1;

        while (left < right) {
            preMax = Math.max(preMax, height[left]);
            sufMax = Math.max(sufMax, height[right]);
            if (preMax < sufMax) {
                ans += preMax - height[left];
                left++;
            } else {
                ans += sufMax - height[right];
                right--;
            }
        }

        return ans;
    }
}