代码训练LeetCode(27)接雨水

代码训练(27)LeetCode之接雨水

Author: Once Day Date: 2025年6月10日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 42. 接雨水 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

1. 原题

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

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

示例 1：

输入：height = [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. 分析

这个问题是关于如何计算一组由柱子组成的高度图在下雨后能够积累的雨水量。每个柱子的宽度都是1个单位，高度由输入数组给出。我们需要找出柱子之间形成的凹槽，这些凹槽会收集雨水。

要解决这个问题，关键在于理解如何计算每个柱子上方可以积累的雨水量。这取决于柱子左右两边的最高柱子的高度。对于数组中的每个元素，找到：

1. 左边最高的柱子。
2. 右边最高的柱子。

对于某个柱子 i，它上方能积累的雨水量由 min(max_left, max_right) - height[i] 给出，其中 max_left 是左边最高柱子的高度，max_right 是右边最高柱子的高度。

分析步骤：

1. 初始化：创建两个数组 left_max 和 right_max 来存储每个位置左边和右边的最大高度。
2. 填充 left_max：从左到右遍历，确保 left_max[i] 存储从左侧到当前位置的最大高度。
3. 填充 right_max：从右到左遍历，确保 right_max[i] 存储从右侧到当前位置的最大高度。
4. 计算积水量：遍历数组，使用 min(left_max[i], right_max[i]) - height[i] 计算每个位置可以积累的雨水量，并将它们累加。

举例分析：以输入 height = [0,1,0,2,1,0,1,3,2,1,2,1] 为例:

• 左最大高度 (left_max): [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
• 右最大高度 (right_max): [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]
• 计算积水: 对于每个位置，使用 min(left_max[i], right_max[i]) - height[i] 计算可能的积水量，如位置2的积水量为 min(1, 3) - 0 = 1。

性能优化关键点

• 空间优化：尽管使用了两个额外的数组来存储左右最大高度，但这是为了避免重复计算，从而优化时间性能。
• 时间复杂度：该解法的时间复杂度为O(n)，因为只需要三次遍历整个数组。
• 空间复杂度：空间复杂度为O(n)，因为我们创建了两个与输入数组同样长度的数组。

3. 代码实现

#include <stdio.h>
#include <stdlib.h>

int trap(int* height, int heightSize) {
    int *left_max = (int*)malloc(heightSize * sizeof(int));
    int *right_max = (int*)malloc(heightSize * sizeof(int));
    int water = 0;

    left_max[0] = height[0];
    for (int i = 1; i < heightSize; i++) {
        left_max[i] = height[i] > left_max[i - 1] ? height[i] : left_max[i - 1];
    }

    right_max[heightSize - 1] = height[heightSize - 1];
    for (int i = heightSize - 2; i >= 0; i--) {
        right_max[i] = height[i] > right_max[i + 1] ? height[i] : right_max[i + 1];
    }

    for (int i = 0; i < heightSize; i++) {
        water += (left_max[i] < right_max[i] ? left_max[i] : right_max[i]) - height[i];
    }

    free(left_max);
    free(right_max);

    return water;
}

int main() {
    int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int n = sizeof(height) / sizeof(height[0]);
    printf("Total trapped rain water is: %d\n", trap(height, n));
    return 0;
}

4. 总结

这个问题考察了数组遍历和空间时间复杂度权衡的能力。通过练习这类问题，可以提高对动态规划和双指针技巧的理解和应用。对于类似问题，一种优化的思路是尝试减少空间的使用，比如通过双指针法直接在原数组上操作以减少空间复杂度。