【算法小记】接雨水的不同解法

在这里插入图片描述
题目连接：https://leetcode.cn/problems/trapping-rain-water/

1、暴力解法

class Solution: def trap(self, height: List[int]) -> int: n = len(height) # 存放总的雨水量 res = 0 # 特判，如果柱子的个数少于3，那不可能接到水 if n<3: return 0 # 因为两个边界的柱子不能接到水，所以只考虑从1到n-2 for i in range(1,n-1): # 找到左边最高的柱子 max_left = 0 for j in range(i-1,-1,-1): if height[j]>max_left: max_left = height[j] # 找到右边最高的柱子 max_right = 0 for j in range(i+1,n): if height[j]>max_right: max_right = height[j] # 短板效应，装水量取决于矮的那个 min_h = min(max_left,max_right) # 只有当左右柱子中矮的那个比当前高度高，才能接到水 if min_h>height[i]: res += min_h-height[i] return res

2.动态规划

相当于用空间换时间了，时间复杂度降低到了O(n)，可以AC。

class Solution: def trap(self, height: List[int]) -> int: n = len(height) res = 0 if n<3: return 0 max_left = [0 for _ in range(n)] max_right = [0 for _ in range(n)] for i in range(1,n-1): max_left[i] = max(max_left[i-1],height[i-1]) for i in range(n-2,0,-1): max_right[i] = max(max_right[i+1],height[i+1]) for i in range(1,n-1): min_h = min(max_left[i],max_right[i]) if min_h>height[i]: res += min_h-height[i] return res

3.双指针

其实是对第二种解法空间复杂度的一个优化，用双指针取代了数组。取代之后就要注意在一次遍历的时候，判断到底是当前柱子左侧的高度更小还是右侧的高度更小，从而决定更新使用的值。具体见代码和注释。

时间复杂度为O(n)，空间复杂度为O（1）

class Solution: def trap(self, height: List[int]) -> int: n = len(height) res = 0 if n<3: return 0 max_left,max_right = 0,0 left,right = 1,n-2 for i in range(1,n-1): # 从左往右更新，因为max_left是由height[left-1]推算出来的，所以当height[left-1]小于height[right+1]的时候，max_left一定小于max_right，右边的同理 if height[left-1]<height[right+1]: max_left = max(max_left,height[left-1]) if max_left>height[left]: res += max_left-height[left] left += 1 else: max_right = max(max_right,height[right+1]) if max_right>height[right]: res += max_right-height[right] right -= 1 return res

4、栈

我们可以参考括号匹配，去计算每一对柱子之间的水量。
用栈去保存高度，遍历的时候如果当前高度小于栈顶高度，那么说明会由积水，我们当前高度的下标入栈。
如果当前高度大于栈顶的高度，那么说明之前的积水到这里停下了，可以计算到底有多少积水了。计算完成后，把当前的墙继续入栈，作为新的积水柱子。
总体原则：
（1）当前高度小于栈顶高度，入栈，指针后移
（2）当前高度大于栈顶高度，出栈，计算当前的柱子和栈顶之间的积水量，然后计算当前高度和新站的高度关系，重复2，直到当前柱子的高度不大于栈顶高度，或者栈为空，然后把当前柱子入栈，指针后移。

class Solution: def trap(self, height: List[int]) -> int: n = len(height) res = 0 if n<3: return 0 stack = [] for i in range(n): # 只要栈不为空而且当前的柱子高度大于栈顶，就可以循环比较计算 while stack and height[i]>height[stack[-1]]: h = height[stack.pop()] if not stack: break distance = i-stack[-1]-1 min_h = min(height[stack[-1]],height[i]) res += distance*(min_h-h) stack.append(i) return res

今天的文章【算法小记】接雨水的不同解法分享到此就结束了，感谢您的阅读。

【算法小记】接雨水的不同解法

1、暴力解法

2.动态规划

3.双指针

4、栈

相关推荐