H 42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:


Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9
 

Constraints:

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

题目翻译：
给定 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 * 10^4
0 <= height[i] <= 10^5



class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1; // 初始化左右指针
        int leftMax = height[0], rightMax = height[height.length - 1]; // 初始化左右最大值
        int water = 0; // 初始化结果为 0，表示蓄水量

        while (left < right) { // 当左指针小于右指针时，进行循环
            if (leftMax < rightMax) { // 如果左侧高度小于右侧高度
                left++; // 将左指针向右移动一位
                if (leftMax < height[left]) { // 如果左侧最大高度小于当前左指针指向的高度
                    leftMax = height[left]; // 更新左侧最大值
                } else { // 否则
                    water += leftMax - height[left]; // 计算雨水量并累加到结果中
                }
            } else { // 如果左侧高度大于等于右侧高度
                right--; // 将右指针向左移动一位
                if (rightMax < height[right]) { // 如果右侧最大高度小于当前右指针指向的高度
                    rightMax = height[right]; // 更新右侧最大值
                } else { // 否则
                    water += rightMax - height[right]; // 计算雨水量并累加到结果中
                }
            }
        }
        return water; // 返回最终蓄水量
    }
}