力扣经典150题第十六题：接雨水

力扣经典150题第十六题：接雨水

1. 题目描述

给定 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

2. 问题分析

接雨水的问题可以使用双指针或者栈来解决。这里我们介绍使用双指针的解法。

3. 解题思路

• 使用两个指针 left 和 right 分别从数组的两端向中间移动。
• 定义变量 left_max 和 right_max 分别表示左侧和右侧的最大高度。
• 使用变量 ans 来累计接到的雨水量。
• 如果 height[left] < height[right]，则更新 left 端，否则更新 right 端。
• 每次移动指针时，更新对应一侧的最大高度，并根据当前柱子的高度和最大高度的关系计算接到的雨水量并累加到 ans 中。

4. 代码实现

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int left_max = 0, right_max = 0;
        int ans = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    ans += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    ans += right_max - height[right];
                }
                right--;
            }
        }
        
        return ans;
    }
}

5. 时间复杂度分析

• 单次遍历数组，时间复杂度为 O(n)。

6. 应用和扩展

• 该算法可以有效地解决接雨水的问题，通过双指针从两侧向中间移动，根据柱子高度的不同情况计算接到的雨水量。
• 可以在实际中应用于计算积水等场景。

7. 总结

本文介绍了如何使用双指针来解决接雨水的问题，通过计算左右两侧的最大高度来确定柱子之间可以接到的雨水量。

8. 参考资料

• LeetCode 官网
• 算法导论