【Leetcode】解题笔记 2 （动态规划）——42.接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水 上面是由数组 [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

解法一：行计算

解题思路

以行方式计算接水高度，假设行数为j，当前高度为height[i]，用temp存储每行一共可以存储的水量，初始为0，设置ans为总储水量，初始为0。 如果height[i] >= j，则说明数组当前高度无法存储水； 如果height[i] < j，则说明当前高度可以存储1个单位的水量，因此temp+=1； 以上图为例，当i=1进行以下步骤： height[0] = 0 < 1, temp = 0； height[1] = 1 >= 1, ans += temp, temp = 0； height[2] = 0 < 1, temp += 1； height[3] = 2 >= 1, ans += temp, temp = 0； height[4] = 1 >= 1, ans += temp, temp = 0； height[5] = 0 < 1, temp += 1； height[6] ~ height[11] 值都大于等于1，因此步骤都为ans += temp, temp = 0；

代码实现

解法一：行计算

class Solution: def trap(self, height: List[int]) -> int: hmax = 0 hl = len(height) for i in range(hl): if height[i] > hmax: hmax = height[i] ans = 0 temp = 0 for i in range(1, hmax + 1): flag = 0 temp = 0 for j in range(hl): if height[j] < i and flag == 1: temp += 1 if height[j] >= i: flag = 1 ans += temp temp = 0 return ans

复杂度分析

时间复杂度 $O(n\ast h)$，其中有$h$行，每行进行$n$次计算。 空间复杂度 $O(1)$。

解法二：列计算

解题思路

对于当前列，只需要关注其左边最高列left_max和右边最高列right_max即可，选择左、右最高列中较矮的一列，即min_num = min(left_max,right_max)。设置ans为总储水量，初始为0。将min_num与当前列height[i]进行对比，有以下两种情况： height[i] < min_num:那么说明当前列可以存储水，水量为min_num-height[i]； height[i] >= min_num:当前列无法存储水，水量为0； 因此对数组的每个高度为ans += max(min_num - height[i],0)

代码实现

class Solution: def trap(self, height: List[int]) -> int: lh = len(height) ans = 0 for i in range(lh): left_max = 0 for j in range(i): if left_max < height[j]: left_max = height[j] right_max = 0 for j in range(lh - 1, i, -1): if right_max < height[j]: right_max = height[j] min_num = min(left_max,right_max) ans += min(0,min_num - height[i]) return ans

复杂度分析

时间复杂度 $O(n^2)$，每个列都要计算一次左边最高列和右边最高列，复杂度为$n$，计算$n$次。 空间复杂度 $O(1)$

解法三：动态规划

解题思路

根据解法二，可以知道，当前高度height[i]只要找到其左边最高列和右边最高列即可，因此解法三可以对解法二进行算法的优化。 left_max[i] 代表第 i 列左边最高的墙的高度，right_maxt[i] 代表第 i 列右边最高的墙的高度，那么可以根据动态规划得到公式如下： left_max[i] = max(left_max[i-1],height[i-1])：前一列的左边的最高列与前一列的高度选较大的，作为当前列左边最高列； right_max[i] = max(right_max[i+1],height[i+1])：后一列的右边的最高列与后一列的高度选较大的，作为当前列右边最高列；

代码实现

class Solution: def trap(self, height: List[int]) -> int: lh = len(height) left_max = [0 for _ in range(lh)] right_max = [0 for _ in range(lh)] ans = 0 for i in range(1,lh): left_max[i] = max(left_max[i-1],height[i-1]) for i in range(lh-2,-1,-1): right_max[i] = max(right_max[i+1],height[i+1]) for i in range(1,lh-1): maxnum = min(left_max[i],right_max[i]) if maxnum > height[i]: ans += maxnum - height[i] return ans

复杂度分析

时间复杂度 $O(n)$，只要计算一次左边最高列和右边最高列并且保存下来即可，复杂度为$1$，计算$n$次。 空间复杂度 $O(n)$