题解 | 接雨水问题

1、解题思路

1. 双指针法： 使用两个指针，一个从左向右移动（left），一个从右向左移动（right）。维护两个变量，left_max和right_max，分别表示从左到右和从右到左遍历时的最大高度。每次移动高度较小的指针，因为较小的高度决定了当前能够接住的雨水量。计算当前柱子的接水量：min(left_max, right_max) - current_height。
2. 动态规划法： 预计算每个柱子左边的最大高度和右边的最大高度。对于每个柱子，接水量为min(left_max[i], right_max[i]) - height[i]。这种方法需要额外的空间存储left_max和right_max数组。
3. 单调栈法： 使用单调栈来维护一个递减的柱子高度序列。当遇到一个比栈顶高的柱子时，计算栈顶柱子能够接住的雨水量。这种方法需要额外的栈空间。

2、代码实现

C++（双指针法）

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        if (arr.empty()) {
            return 0;
        }

        int left = 0, right = arr.size() - 1;
        int left_max = arr[left], right_max = arr[right];
        int water = 0;

        while (left < right) {
            if (left_max < right_max) {
                left++;
                left_max = max(left_max, arr[left]);
                water += left_max - arr[left];
            } else {
                right--;
                right_max = max(right_max, arr[right]);
                water += right_max - arr[right];
            }
        }

        return water;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        if (arr.length == 0) return 0;

        int left = 0, right = arr.length - 1;
        int leftMax = arr[left], rightMax = arr[right];
        int water = 0;

        while (left < right) {
            if (leftMax < rightMax) {
                left++;
                leftMax = Math.max(leftMax, arr[left]);
                water += leftMax - arr[left];
            } else {
                right--;
                rightMax = Math.max(rightMax, arr[right]);
                water += rightMax - arr[right];
            }
        }

        return water;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here
        if not arr:
            return 0
        
        left, right = 0, len(arr) - 1
        left_max, right_max = arr[left], arr[right]
        water = 0
        
        while left < right:
            if left_max < right_max:
                left += 1
                left_max = max(left_max, arr[left])
                water += left_max - arr[left]
            else:
                right -= 1
                right_max = max(right_max, arr[right])
                water += right_max - arr[right]
        
        return water

3、复杂度分析

1. 双指针法： 通过移动两个指针，每次处理较小的那个指针，确保当前柱子能够接住的雨水量由较小的最大高度决定。时间复杂度：O(n)，空间复杂度：O(1)。
2. 动态规划法： 需要额外的O(n)空间存储left_max和right_max数组。时间复杂度：O(n)，空间复杂度：O(n)。
3. 单调栈法： 使用栈来维护递减的柱子高度，适合处理复杂的高度变化。时间复杂度：O(n)，空间复杂度：O(n)。