本文主要是介绍[LeetCode] 42. Trapping Rain Water @ python,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一.题目:
给一个数组,里面都是非负数,求它们困住的水的最大体积是多少?
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
二.解题思路:
确定一个位置所能存住的水的体积是由其两边的较短的那根柱子决定的.所以我们首先确定两个变量left_max,right_max,并在遍历数组时更新它们的值.
代码如下:
class Solution(object):def trap(self, height):""":type height: List[int]:rtype: int"""left = 0right = len(height) - 1left_max = right_max = water = 0#left_max 表示左边的最大值,right_max表示右边的最大值while left <= right:if left_max <= right_max:left_max = max(left_max, height[left])water += left_max - height[left]left += 1else:right_max = max(right_max, height[right])water += right_max - height[right]right -= 1return water
这篇关于[LeetCode] 42. Trapping Rain Water @ python的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!