免费服装网站模板,优舟网站建设,东昌府做网站,深圳企业网站制作企业问题描述:
给定m个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子下雨之后能储存多少水. 思路解析:
思考一下,什么样的位置能盛水?只有在当前柱子的左边和右边都比它高的情况下才能储存住水,而储水量和左侧最高柱及右侧最高柱有关.具体来说就是和左右两侧最矮的…问题描述:
给定m个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子下雨之后能储存多少水. 思路解析:
思考一下,什么样的位置能盛水?只有在当前柱子的左边和右边都比它高的情况下才能储存住水,而储水量和左侧最高柱及右侧最高柱有关.具体来说就是和左右两侧最矮的高度直接相关.变量如下:
height变量:表示输入的柱高度组
left变量:表示左指针指向的柱,初始值为0
right变量:表示右指针指向的柱,初始值为0
leftmax变量:表示左指针所指的左边最高的柱高
rightmax变量:表示右指针所指的柱右边最高的柱高
res变量:表示输出结果
完整代码如下:
def water(self, height): # 定义一个名为water的方法接收一个列表height作为参数left 0 # 初始化左指针为0right len(height) - 1 # 初始化右指针为列表的最后一个元素的索引leftmax rightmax 0 # 初始化左右两边的最大高度为0res 0 # 初始化结果res为0用于累积能够容纳的水的总量while left right: # 当左指针小于右指针时继续循环if height[left] height[right]: # 如果左边的高度小于右边的高度if height[left] leftmax: # 如果当前左边的高度大于等于左边的最大高度leftmax height[left] # 更新左边的最大高度else: # 如果当前左边的高度小于左边的最大高度res leftmax - height[left] # 计算当前位置可以添加的水并累加到resleft 1 # 移动左指针else: # 如果左边的高度不小于右边的高度即大于或等于if height[right] rightmax: # 如果当前右边的高度大于等于右边的最大高度rightmax height[right] # 更新右边的最大高度else: # 如果当前右边的高度小于右边的最大高度res rightmax - height[right] # 计算当前位置可以添加的水并累加到resright - 1 # 移动右指针return res # 返回最终计算出的水量
