接雨水

题目要求

给定一个数组，它的第 i 个元素表示一个宽度为 1 的柱子的高度。这些柱子按照顺序排列，形成一个高度图。当下雨时，柱子之间的凹槽可能会积水。需要编写一个算法来计算整个高度图在一场雨后能够接多少单位的雨水。

解题思路

要解决这个问题，我们可以通过以下步骤来逐步逼近解决方案：

理解问题：首先要明白雨水能够积存的地方是在连续的柱子之间形成的凹槽中。雨水的多少取决于凹槽的深度和宽度，而凹槽的深度又取决于凹槽两边柱子的高度。
找到边界：对于数组中的任意一个位置，能积水的量取决于它左边和右边最高的柱子的高度（不包括它自己）。因此，对于每个位置，我们需要知道其左边最高的柱子和右边最高的柱子。
计算积水量：对于数组中的每个元素，我们计算左边最高的柱子和右边最高的柱子，取二者之间较小的一个，然后减去当前柱子的高度，就得到了当前位置能积水的量。如果计算结果为负数，则表示当前位置不会积水，积水量为 0。
优化存储：为了避免重复计算，我们可以使用两个数组来分别存储每个位置左边最高的柱子和右边最高的柱子。这样，我们只需要遍历一次数组就可以计算出所有位置的积水量。
总结积水量：最后，我们将所有位置的积水量相加，就得到了整个高度图能接的雨水总量。
边界条件处理：在实际编码时，还需要注意处理数组的边界条件，例如数组为空或只有一个元素时，显然不会积水。

通过以上步骤，我们可以得到一个有效的算法来解决这个问题。注意，这个问题也可以通过栈或双指针等方法来解决，但上述方法是最直观和容易理解的。

Golang 版本

package main

import (
	"fmt"
)

func trap(height []int) int {
	if len(height) == 0 {
		return 0
	}

	leftMax := make([]int, len(height))
	rightMax := make([]int, len(height))

	// Fill leftMax array
	leftMax[0] = height[0]
	for i := 1; i < len(height); i++ {
		leftMax[i] = max(height[i], leftMax[i-1])
	}

	// Fill rightMax array
	rightMax[len(height)-1] = height[len(height)-1]
	for i := len(height) - 2; i >= 0; i-- {
		rightMax[i] = max(height[i], rightMax[i+1])
	}

	// Calculate total trapped water
	water := 0
	for i := 0; i < len(height); i++ {
		water += min(leftMax[i], rightMax[i]) - height[i]
	}

	return water
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	height := []int{0,1,0,2,1,0,1,3,2,1,2,1}
	fmt.Println("Total trapped water:", trap(height))
}

这段代码定义了一个trap函数，它接受一个整数数组height作为输入，代表柱子的高度图，并返回一个整数，代表按此排列的柱子，下雨之后能接多少雨水。主函数main中给出了一个示例输入，并打印出计算的结果。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int trap(const std::vector<int>& height) {
    if (height.empty()) {
        return 0;
    }

    int n = height.size();
    std::vector<int> leftMax(n), rightMax(n);
    int waterTrapped = 0;

    leftMax[0] = height[0];
    for (int i = 1; i < n; ++i) {
        leftMax[i] = std::max(leftMax[i - 1], height[i]);
    }

    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        rightMax[i] = std::max(rightMax[i + 1], height[i]);
    }

    for (int i = 0; i < n; ++i) {
        waterTrapped += std::min(leftMax[i], rightMax[i]) - height[i];
    }

    return waterTrapped;
}

int main() {
    std::vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
    std::cout << "Total trapped water: " << trap(height) << std::endl;
    return 0;
}

这段 C++代码实现了一个trap函数，它接受一个整数类型的std::vector作为输入，代表柱子的高度图，并返回一个整数，代表按此排列的柱子，下雨之后能接多少雨水。main函数中给出了一个示例输入，并打印出计算的结果。

Python 版本

def trap(height):
    if not height:
        return 0

    n = len(height)
    left_max, right_max = [0] * n, [0] * n
    water_trapped = 0

    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    for i in range(n):
        water_trapped += min(left_max[i], right_max[i]) - height[i]

    return water_trapped

# Example usage:
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(f"Total trapped water: {trap(height)}")

这段 Python 代码定义了一个trap函数，它接受一个列表height作为输入，代表柱子的高度图，并返回一个整数，代表按此排列的柱子，下雨之后能接多少雨水。在代码的最后，给出了一个示例输入，并打印出计算的结果。

Java 版本

public class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        int waterTrapped = 0;

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        for (int i = 0; i < n; i++) {
            waterTrapped += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return waterTrapped;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("Total trapped water: " + solution.trap(height));
    }
}

这段 Java 代码定义了一个Solution类，其中包含一个trap方法用于计算接雨水的总量。trap方法接受一个整型数组height作为输入，代表柱子的高度图，并返回一个整数，代表按此排列的柱子，下雨之后能接多少雨水。main方法中给出了一个示例输入，并打印出计算的结果。

Rust 版本

fn trap(height: Vec<i32>) -> i32 {
    let n = height.len();
    if n == 0 {
        return 0;
    }

    let mut left_max = vec![0; n];
    let mut right_max = vec![0; n];
    let mut water_trapped = 0;

    left_max[0] = height[0];
    for i in 1..n {
        left_max[i] = std::cmp::max(left_max[i - 1], height[i]);
    }

    right_max[n - 1] = height[n - 1];
    for i in (0..n - 1).rev() {
        right_max[i] = std::cmp::max(right_max[i + 1], height[i]);
    }

    for i in 0..n {
        water_trapped += std::cmp::min(left_max[i], right_max[i]) - height[i];
    }

    water_trapped
}

fn main() {
    let height = vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
    println!("Total trapped water: {}", trap(height));
}

这段 Rust 代码定义了一个trap函数，它接受一个Vec<i32>类型的向量height作为输入，代表柱子的高度图，并返回一个i32类型的整数，代表按此排列的柱子，下雨之后能接多少雨水。main函数中给出了一个示例输入，并打印出计算的结果。

总结

上述解法采用了动态规划的思想来解决接雨水问题。核心思路是对于高度图中的每个位置，找出其左侧和右侧的最大高度，这两个值决定了当前位置能够积水的最大高度。具体步骤如下：

初始化两个数组left_max和right_max，分别用来存储每个位置左侧和右侧的最大高度。
从左到右遍历高度图，更新left_max数组，使得left_max[i]存储height[0..i]中的最大值。
从右到左遍历高度图，更新right_max数组，使得right_max[i]存储height[i..n-1]中的最大值。
再次遍历高度图，对于每个位置，计算左侧和右侧最大高度的较小值，然后减去当前位置的高度，得到当前位置的积水量。如果计算结果小于零，则当前位置积水量为零。
将所有位置的积水量累加，得到整个高度图的总积水量。

这种方法的时间复杂度为 O(n)，因为每个元素只需要遍历一次来构建left_max和right_max数组，然后再遍历一次来计算积水量。空间复杂度也为 O(n)，因为需要额外的空间来存储左侧和右侧的最大高度数组。

hot-100