42.接雨水 python实现

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

解题思路

• 分析：接雨水的结构需要两个边界，所以采用双指针。取两个边界的最小值为最终边界的高，雨水的面积等于边界的高乘以两个边界之间的距离，再减去两个边界之间所有柱子的面积。
• 步骤：
  1.在遍历数组的时候寻找两个边界，并记录两个边界的位置。
  2.定义一个左指针，从左往右，记录左边最高的柱子高度，生成left_max数组；同理定义一个右指针，从右往左遍历，记录右边最高的柱子高度，生成right_max数组。
  3.对每一个位置计算min(left_max[i], right_max[i]) - 当前位置柱子的高度heigh[i]

class Solution(object):def trap(height):"""type height:List[int]:return: int"""n = len(height)if n <= 2:return 0    #边界条件判断，柱子不少于3个left, right = 0, n -1 #左右指针res = 0     #所能接的雨水面积left_max = 0    #左边最高的柱子的初始位置right_max = len(height) - 1 #右边最高柱子的初始位置while left < right:if height[left] > height[right]: #如果右边柱子高度低于左边柱子，则右指针往前移if height[right_max] < height[right]:#遍历更新右边最高柱子的位置right_max = rightright -= 1else:res += height[right_max] - height[right]    #累加右边积的雨水面积right -= 1else:if height[left_max] <height[left]:left_max = left #更新左边最高柱子的位置left += 1else:res += height[left_max] - height[left]  #累加左边积的雨水面积left += 1return res#测试if __name__ == "__main__":height = list(map(int, input().strip().split()))print(trap(height))

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！