Matarialize中文社区-LeetCode 热题 100专栏

接雨水

栈,数组,双指针,动态规划,单调栈

给定 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 * 104
0 <= height[i] <= 105

解法一：

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let left = 0;
    let right = height.length - 1;
    let sum = 0;
    let leftMax = 0;
    let rightMax = 0;
    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                sum += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                sum += rightMax - height[right];
            }
            right--;
        }
    }

    return sum;
};

说明：

要计算给定柱子高度图中的接雨水量，我们可以使用双指针的方法进行计算。这个问题通常被称为“接雨水问题”（Trapping Rain Water Problem）。

方法：双指针

算法步骤

初始化指针和变量：

左指针 left 指向数组的开始位置（索引 0）。
右指针 right 指向数组的结束位置（索引 n-1）。
初始化 left_max 和 right_max 分别为柱子高度的初始左端和右端。
初始化 water_trapped 变量为 0，用于存储总的接雨水量。

遍历柱子高度数组：

如果 height[left] 小于等于 height[right]：
否则：

如果 height[left] 大于等于 left_max，则更新 left_max。
否则，计算当前位置能接的水量为 left_max - height[left]，并将该水量累加到 water_trapped。
移动左指针，即 left 增加 1。

如果 height[right] 大于等于 right_max，则更新 right_max。
否则，计算当前位置能接的水量为 right_max - height[right]，并将该水量累加到 water_trapped。
移动右指针，即 right 减少 1。
当 left 小于 right 时，进行以下操作：

返回结果：

当循环结束时，water_trapped 即为接雨水的总量。

算法实现

下面是用 Python 实现的代码：

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

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water_trapped = 0

    while left < right:
        if height[left] <= height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water_trapped += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water_trapped += right_max - height[right]
            right -= 1

    return water_trapped
# 示例
height = [0,1,0,2,1,0,1,3,2,1,2,1]
result = trap(height)
print("能接的雨水总量:", result)

示例

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

解释

在这个例子中，按照这种高度排列的柱子，经过雨水积累后，能够接住的雨水总量为 6。

复杂度分析

时间复杂度：O(n)，其中 n 是柱子高度数组的长度。我们只需遍历一次数组。
空间复杂度：O(1)，除了存储变量外，不需要额外的空间。

这种方法有效地利用了双指针技巧，通过一次遍历即可完成对接雨水量的计算，是解决该问题的常用方法之一。

评论区

字数统计

评论列表