42. 接雨水

题目

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

示例 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：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

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

代码

完整代码

#include <stdbool.h>

int trap(int* height, int heightSize) {
    int water = 0;
    bool needRoute = false;
    int lastLeftIndex = -1;
    int level = 1;
    for (int i = 0; i < heightSize; i++)
    {
        if(height[i] >= level)
        {
            if(height[i] > level)
            {
                needRoute = true;
            }
            if(lastLeftIndex == -1)
            {
            }
            else
            {
                water += (i - lastLeftIndex - 1) > 0 ? (i - lastLeftIndex - 1) : 0;
                if(((i - lastLeftIndex - 1) > 0 ? (i - lastLeftIndex - 1) : 0) > 0)
                {
                    // printf("index %d, level %d\n",i, level);
                    // printf("water += %d \n",(i - lastLeftIndex - 1));
                }
            }
            // printf("index %d, level %d\n",i, level);
            // printf("left wall refresh %d\n",height[i]);
            lastLeftIndex = i;
        }
        if(i == heightSize - 1)
        {
            level++;
            lastLeftIndex = -1;
            if(needRoute)
            {
                needRoute = false;
                i = -1;
            }
        }
    }
    return water;
}

思路分析

1. 按层遍历：从第一层（高度为 1）开始，逐层扫描，计算每一层的雨水量。
2. 水位标记：对于每一层，遍历数组，记录当前层的左右墙壁以及水平距离，计算当前层的雨水量。
3. 累加求和：将每一层的雨水量累加，得到总的雨水量。
4. 时间复杂度：考虑每一层的遍历，总的时间复杂度为 O(n * h)，其中 n 是数组 height 的长度，h 是数组 height 的最大值。

拆解分析

• 按层遍历：从高度为 1 开始，逐层向上扫描。
• 水位标记：对于每一层，记录左右墙壁以及水平距离，计算当前层的雨水量。
• 累加求和：将每一层的雨水量累加，得到总的雨水量。

复杂度分析

• 时间复杂度：考虑每一层的遍历，总的时间复杂度为 O(n * h)，其中 n 是数组 height 的长度，h 是数组 height 的最大值。
• 空间复杂度：O(1)，只使用常数级别的额外空间。

结果

一题多解

双指针法

代码

#define MIN(a,b) ((a) < (b) ? (a) : (b))

int trap(int* height, int heightSize) {
    if (heightSize <= 2) return 0; // 边界情况处理

    int water = 0;
    int left = 0, right = heightSize - 1;
    int lefth = 0, righth = 0;
    int totalsize = 0;

    while (left < right) {
        if (height[left] <= height[right]) { // 左边界小于等于右边界
            if (height[left] >= lefth) {
                lefth = height[left]; // 更新左边界的高度
            } else {
                water += lefth - height[left]; // 累加雨水量
            }
            left++; // 左边界右移
        } else { // 右边界小于左边界
            if (height[right] >= righth) {
                righth = height[right]; // 更新右边界的高度
            } else {
                water += righth - height[right]; // 累加雨水量
            }
            right--; // 右边界左移
        }
    }

    return water;
}

思路分析

• 双指针法：使用左右两个指针向中间靠拢，分别记录左右两侧的最大高度。
• 水位标记：遍历数组，通过比较左右两侧的最大高度来确定当前位置能够存储的雨水量。

拆解分析

• 双指针移动：左右指针向中间移动，同时更新左右两侧的最大高度。
• 计算存水量：根据左右两侧的最大高度和当前柱子的高度，确定当前位置的存水量。
• 结束条件：左右指针相遇时结束遍历。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 height 的长度。
• 空间复杂度：O(1)，只使用常数级别的额外空间。

结果