Python口试宝典第22题：接雨水

题目

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

1. 输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
2. 输出：6
3. 解释：下面是由数组表示的高度图，在这种情况下，可以接6个单位的雨水（蓝色部分表示雨水）。

复制代码

        示例 2：

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

复制代码

暴力法

        暴力法求解本题的基本头脑是：遍历每个柱子，对于每个柱子，分别向其左右两侧探求最高的柱子；然后，用这个最高柱子的高度减去当前柱子的高度，得到大概蓄水的高度。利用暴力法求解本题的主要步骤如下。
        1、初始化结果变量total_rain为0，用于累加盘算接住的雨水量。
        2、遍历每个柱子的位置i，进行如下操作。
        （1）找到位置i左侧的最大高度max_left，初始为0。
        （2）找到位置i右侧的最大高度max_right，初始为0。
        （3）向左遍历，更新max_left为左侧遇到的最大高度。
        （4）向右遍历，更新max_right为右侧遇到的最大高度。
        （5）盘算当前位置能接住的雨水量：min(max_left, max_right) - height，并累加到total_rain中。
          3、返回最终的total_rain作为结果。
          根据上面的算法步骤，我们可以得出下面的示例代码。

1. def trap_rainwater_by_brute_force(height):
2.     n = len(height)
3.     total_rain = 0
4.    
5.     for i in range(n):
6.         max_left, max_right = 0, 0
7.         
8.         # 寻找左侧最大高度
9.         for j in range(i, -1, -1):
10.             max_left = max(max_left, height[j])
11.         
12.         # 寻找右侧最大高度
13.         for j in range(i, n):
14.             max_right = max(max_right, height[j])
15.         
16.         # 当前柱子能接住的雨水量
17.         rain = min(max_left, max_right) - height[i]
18.         
19.         # 累加雨水量
20.         total_rain += rain if rain > 0 else 0
21.    
22.     return total_rain
24. height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
25. print(trap_rainwater_by_brute_force(height))
27. height = [4, 2, 0, 3, 2, 5]
28. print(trap_rainwater_by_brute_force(height))

复制代码

动态规划法

        动态规划法求解本题的基本头脑是：从左到右、从右到左各遍历一次数组，分别盘算出到当前位置为止的最高柱子高度，并利用这两个信息来确定当前位置能存多少雨水。利用动态规划法求解本题的主要步骤如下。
        1、初始化两个数组 leftMax 和 rightMax，长度与原数组相同。leftMax 存储索引 i 左侧（包括 i）的柱子中的最大高度，而 rightMax 存储索引 i 右侧（包括 i）的柱子中的最大高度。
        2、先从左向右遍历一次 height 数组，更新 leftMax 数组。对于每个位置 i，如果 height 大于当前的 leftMax[i-1]，则 leftMax = height；否则 leftMax = leftMax[i-1]。
        3、再从右向左遍历一次 height 数组，更新 rightMax 数组。对于每个位置 i，如果 height 大于当前的 rightMax[i+1]，则 rightMax = height；否则 rightMax = rightMax[i+1]。
        4、遍历 height 数组，对于每个位置 i，盘算能接的雨水量为 min(leftMax, rightMax) - height，并累加这些值作为最终结果。
        根据上面的算法步骤，我们可以得出下面的示例代码。

1. def trap_rainwater_by_dp(height):
2.     n = len(height)
3.     leftMax = [0] * n
4.     rightMax = [0] * n
5.     waterTrap = 0
7.     # 从左到右计算 leftMax
8.     leftMax[0] = height[0]
9.     for i in range(1, n):
10.         leftMax[i] = max(leftMax[i-1], height[i])
12.     # 从右到左计算 rightMax
13.     rightMax[n-1] = height[n-1]
14.     for i in range(n-2, -1, -1):
15.         rightMax[i] = max(rightMax[i+1], height[i])
17.     # 计算雨水量
18.     for i in range(n):
19.         waterTrap += min(leftMax[i], rightMax[i]) - height[i]
21.     return waterTrap
23. height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
24. print(trap_rainwater_by_dp(height))
26. height = [4, 2, 0, 3, 2, 5]
27. print(trap_rainwater_by_dp(height))

复制代码

双指针法

        双指针法求解本题的基本头脑是：利用两个指针从数组的两端开始向中心移动，同时维护两个变量来记载左右双方的最大高度。这样可以在遍历过程中直接盘算每个位置能接住的雨水量，而无需提前盘算完整的左右最大高度数组。利用双指针法求解本题的主要步骤如下。
        1、初始化两个指针 left 和 right 分别指向数组的开始和结束。
        2、初始化两个变量 max_left 和 max_right 分别生存 left 和 right 指针所在位置左侧和右侧的最大高度，初始值都设为0。
        3、用一个变量 water 来累计能接住的雨水量。
        4、当 left < right 时，进行以下步骤。
        （1）如果 height[left] < height[right]，说明当前能接雨水的量受限于 height[left]。因此，更新 max_left 为 max(max_left, height[left])，并且累加到 water 中的雨水量为 max_left - height[left]。然后，将 left 指针向右移动一位。
        （2）反之，如果 height[left] >= height[right]，说明当前能接雨水的量受限于 height[right]。因此，更新 max_right 为 max(max_right, height[right])，累加到 water 中的雨水量为 max_right - height[right]，并将 right 指针向左移动一位。
        5、当 left >= right 时，遍历结束，返回累积的雨水量 water。
        根据上面的算法步骤，我们可以得出下面的示例代码。

1. def trap_rainwater_by_two_pointers(height):
2.     left, right = 0, len(height) - 1
3.     max_left, max_right = 0, 0
4.     water = 0
6.     while left < right:
7.         if height[left] < height[right]:
8.             if height[left] >= max_left:
9.                 max_left = height[left]
10.             else:
11.                 water += max_left - height[left]
12.             left += 1
13.         else:
14.             if height[right] >= max_right:
15.                 max_right = height[right]
16.             else:
17.                 water += max_right - height[right]
18.             right -= 1
20.     return water
22. height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
23. print(trap_rainwater_by_two_pointers(height))
25. height = [4, 2, 0, 3, 2, 5]
26. print(trap_rainwater_by_two_pointers(height))

复制代码

总结

        暴力法通过遍历每个柱子，分别盘算其左右双方的最大高度，从而确定当前位置能储存的雨水量。这种方法简朴直接，但服从低下，时间复杂度为O(n^2)，不适用于大规模数据。
        动态规划法利用两个数组分别记载从左到右和从右到左扫描过程中的最大高度，然后遍历每个柱子，盘算雨水量。这种方法相比暴力法明显进步了服从，时间复杂度为O(n)，空间复杂度也为O(n)。
        双指针法现实上是一种优化后的动态规划法，不必要额外存储空间。利用两个指针从数组两端开始向中心移动，同时维护两个变量记载左右双方的最大高度。该方法同样具有O(n)的时间复杂度，但空间复杂度降为O(1)。


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。