42. 接雨水

### 关于接雨水问题的 Java 实现 接雨水问题是经典的算法题目之一，其核心在于通过某种方式计算柱子之间的凹槽部分能够存储的水量。以下是基于 **单调栈** 和 **双指针法** 的两种常见解决方案。 --- #### 方法一：单调栈实现 单调栈是一种有效的数据结构用于处理此类区间极值问题。具体逻辑如下： 1. 使用 `Stack<Integer>` 存储柱子索引。 2. 遍历数组中的每一个柱子高度，当遇到当前柱子高于栈顶柱子时，则说明形成了一个可以积水的区域。 3. 计算该区域内的积水量并累加到总结果中。 下面是完整的代码实现： ```java import java.util.Stack; class Solution { public int trap(int[] height) { Stack<Integer> stack = new Stack<>(); int res = 0; for (int i = 0; i < height.length; i++) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int top = stack.pop(); // 当前要计算面积的位置 if (stack.isEmpty()) break; int distance = i - stack.peek() - 1; // 左右边界距离 int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top]; res += distance * boundedHeight; } stack.push(i); } return res; } } ``` 这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)[^1]。 --- #### 方法二：双指针优化 双指针法利用两个变量分别记录左侧最大值和右侧最大值，在遍历时逐步更新这些值，并根据当前位置的高度差来决定是否增加水体积。 以下是具体的代码实现： ```java class Solution { public int trap(int[] height) { int left = 0, right = height.length - 1; int lMax = 0, rMax = 0; int water = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= lMax) { lMax = height[left]; } else { water += lMax - height[left]; } left++; } else { if (height[right] >= rMax) { rMax = height[right]; } else { water += rMax - height[right]; } right--; } } return water; } } ``` 这种解法时间复杂度同样为 O(n)，但仅需常量级额外空间 O(1)[^2]。 --- #### 提供的代码分析 对于您给出的代码片段[^3]，存在一些潜在改进之处： - 函数 `maxRight` 被多次调用，每次都会重新扫描右边的最大值，增加了不必要的开销。 - 可以考虑采用上述提到的方法进一步提升效率。 --- ### 总结 无论是使用单调栈还是双指针方法都可以高效解决问题。前者更直观易懂；后者则更加节省内存资源。实际应用可根据需求选择合适的方式。