云博
二刷leetcode第42题---接雨水

阅读量:(60) 您现在所在的位置: 首页 百宝箱 Leetcode 二刷leetcode第42题---接雨水 作者:慎独、
简介:二刷leetcode第42题---接雨水 (木桶效应+动态规划)

题目: Leetcode 42.接雨水 (二刷) (困难)

解题思路

本题的一个核心之一是木桶效应:取一个柱子两端较短的那个用作积水的参考。

核心之二是先选出最高的一个木板,然后分别从两边向最高木板过度,根据条件计算出积水量。

采用动态规划:

① 状态定义:即定义我们需要的参数,本地需要求最大积水量,可以看出是求全局最优解。因此我们定义一个 total_water来存储积水的最大值。left记录了每次动态计算的当前柱子左边的最高值,right记录了每次动态计算的当前 柱子右边的最高值。

② 状态转移方程:left = max(left,height[i-1]),right = max(right,height[i+1])

③ 初始化:首先去除首尾为0的值,计算出最高的柱子的索引。left=0,right=0

④ 选取结果:选取total_water作为最高的积水量

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        """木桶效应"""
        if not height:
            return 0
        # 求得最高的那一个大柱子的索引
        top_column = height.index(max(height))
        for i in range(top_column):
            if height[i] != 0:
                del height[:i]
                break
        for j in range(len(height)-1,top_column,-1):
            if height[j] != 0:
                del height[j+1:]
                break
        # 遍历最高值左边
        top_column = height.index(max(height))
        total_water = 0
        left = 0
        # 动态计算最大值
        # 遍历最高值左边
        for i in range(1,top_column):
            # 当前位置的前一个柱子的和其前面的最大值比较
            left = max(height[i-1],left)
            if height[i] < left:
                total_water += left-height[i]
        # 遍历最高值右边
        right = 0
        for i in range(len(height)-2,top_column,-1):
            right = max(height[i+1],right)
            if height[i] < right:
                total_water += right-height[i]
        return total_water

点赞一波

0

    欢迎您游客

 小云标签


 网站统计:


笔记数: 总点赞量:

总访问量:   分类数目:

服务器:阿里云服务器

 网站动态: