LeetCode|LeetCode 42. Trapping Rain Water-五秒内就能理解的O(n)思路
原题链接
https://leetcode-cn.com/probl...
解题思路
我们首先找出数组height中最高墙（top）的位置（top_index）。那么，对于墙的左侧部分，right_max已经确定；对于墙的右侧，left_max已经确定（都等于top）。 之后对左右侧分别求蓄水量，期间分别维护left_max和right_max即可。
【LeetCode|LeetCode 42. Trapping Rain Water-五秒内就能理解的O(n)思路】欢迎在我的博客轻松探索更多思路
代码
class Solution:
def trap(self, height: List[int]) -> int:result=0
if len(height)<3:
return 0top=max(height)
top_index=height.index(max(height))
max_left=height[0]
max_right=height[-1]if top_index>=1:
for i in range(1,top_index,1):
result+=max(0,min(max_left,top)-height[i])
max_left=max(max_left,height[i])if top_index推荐阅读
- LeetCode|LeetCode 102. Binary Tree Level Order Traversal
- LeetCode编程题解法汇总|力扣解法汇总599-两个列表的最小索引总和
- [Golang]力扣Leetcode—剑指Offer—数组—53 - II. 0～n-1中缺失的数字（求和、二分法）
- 每日leetcode——42. 接雨水
- [Golang]力扣Leetcode—剑指Offer—数组—53|[Golang]力扣Leetcode—剑指Offer—数组—53 - I. 在排序数组中查找数字 I（哈希表、遍历）
- Leetcode3无重复字符的最长子串(滑动窗口解法)
- Leetcode|leetcode-蜡烛之间的盘子(经典空换时)
- 每日leetcode——739. 每日温度
- Leetcode120三角形最小路径和
- LeetCode编程题解法汇总|力扣解法汇总258-各位相加