Trapping Rain Water Problem in Java

这个问题简单地被称为“接雨水”，它是著名的经典算法问题之一，用于估算一系列连续的山丘（以条形表示，高度可变）之间所能积聚的雨水量。

如果用非负数数组表示，每个元素代表一个条形在地形图中的高度。问题在于，当考虑相邻条形的高度时，水能在任何一个条形上堆积多少。

这个问题不仅能增进对数组和算法的理解，还能让人了解在编程语言（尤其是Java）中更有效地处理数据和解决问题的方法。

问题陈述

假设给定的数组 height 包含 height[i] 作为索引 i 处条形的高度，那么每个条形上积聚的水量取决于其左侧和右侧最高的条形。可以通过以下公式计算一个条形上方积聚的水量：

其中

left_max[i] 是条形 i 左侧所有条形的最大高度。

right_max[i] 是索引 i 右侧可能找到的所有条形的最大高度。

解决该问题的方法

在 Java 中解决这个问题有两种常见方法：使用辅助数组和使用双指针技术。本文将重点介绍这两种方法的描述，并分别进行说明。

方法一：使用数组

这种方法包括创建 leftMax 数组和 rightMax 数组，分别存储从左侧和右侧的最大高度。

文件名：TrappingRainWater.java

输出

 
Maximum water that can be accumulated is 6   

方法二：使用双指针

双指针技术通过不需要其他数组来提高空间复杂度。它只使用了两个指针，这两个指针从两端开始遍历地形图，然后向中间移动。

文件名：TrappingRainWater.java

输出

 
Maximum water that can be accumulated is 6   

复杂度分析

时间复杂度

• 数组法：O(N)，其中 N 是给定输入数组的元素数量。
• 双指针法：O(N)。

空间复杂度

• 数组法：O(N)，因为额外的数组存储了不同的对象或元素。
• 双指针法：O(1)，因为其操作依赖于常量空间的大小。

结论

这两种方法都允许通过给定的地形图正确估算积聚的雨水总量。它们都可以根据您对数据的时间和空间复杂度要求进行选择。这主要是因为双指针方法占用的空间更少，并且时间复杂度为 O(n)。