接雨水

题目分析

给定一组柱子高度的数组 height，需要计算这些柱子之间能够接住的雨水总量。直观来看，每个柱子上方能够存多少雨水，取决于其左右两侧的最高柱子的高度。

解题思路

本题可以使用 双指针法 进行求解，主要思路如下：

1. 维护两个指针 left 和 right，分别指向数组的左右两端。
2. 维护两个变量 left_max 和 right_max，分别表示当前位置左侧和右侧的最大高度。
3. 如果 height[left] < height[right]，说明 left 侧的最大值决定了 left 位置能接多少水：
   • 如果 height[left] >= left_max，更新 left_max。
   • 否则，当前位置能够接 left_max - height[left] 单位的水。
   • left 指针右移。
4. 反之，如果 height[right] <= height[left]，说明 right 侧的最大值决定了 right 位置能接多少水：
   • 如果 height[right] >= right_max，更新 right_max。
   • 否则，当前位置能够接 right_max - height[right] 单位的水。
   • right 指针左移。
5. 继续上述过程，直到 left 和 right 相遇。

复杂度分析

• 由于整个数组只遍历了一遍，时间复杂度为 O(n)。
• 只使用了常数级别的额外空间，空间复杂度为 O(1)。

代码实现

Python 代码

class Solution:
    def trap(self, height):
        if not height:
            return 0
        
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        water = 0
        
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    water += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    water += right_max - height[right]
                right -= 1
        
        return water

# 读取输入并处理
if __name__ == "__main__":
    n = int(input())
    height = list(map(int, input().split()))
    solution = Solution()
    print(solution.trap(height))

Java 代码

import java.util.Scanner;

public class Main {
    public class Solution {
        public int trap(int[] height) {
            if (height == null || height.length == 0) {
                return 0;
            }
            
            int left = 0, right = height.length - 1;
            int leftMax = 0, rightMax = 0, water = 0;
            
            while (left < right) {
                if (height[left] < height[right]) {
                    if (height[left] >= leftMax) {
                        leftMax = height[left];
                    } else {
                        water += leftMax - height[left];
                    }
                    left++;
                } else {
                    if (height[right] >= rightMax) {
                        rightMax = height[right];
                    } else {
                        water += rightMax - height[right];
                    }
                    right--;
                }
            }
            
            return water;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] height = new int[n];
        for (int i = 0; i < n; i++) {
            height[i] = scanner.nextInt();
        }
        scanner.close();
        
        Main main = new Main();
        Solution solution = main.new Solution();
        System.out.println(solution.trap(height));
    }
}

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;

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

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    water += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    water += right_max - height[right];
                }
                right--;
            }
        }

        return water;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> height(n);
    for (int i = 0; i < n; i++) {
        cin >> height[i];
    }

    Solution solution;
    cout << solution.trap(height) << endl;

    return 0;
}

Leetcode 7.接雨水-原题链接

题目内容

给定$n$个非负整数表示每个宽度为 $1$的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入描述

输入共两行。

• 第一行为两个个整数$n$，代表数组$height$的长度。

• 第二行为$n$个整数$height_0,height_1,...,height_{n-1}$，数字之间以空格分隔。

输出描述

一个整数，表示答案。

样例1

输入

12
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

输入

6
4 2 0 3 2 5

输出

9

提示

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