栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

接雨水 四种解法(Python)

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

接雨水 四种解法(Python)

LeetCode链接

计算每一列可以接的雨水 对每一列 寻找其左右的最大高度 时间复杂度 O(N^2)
class Solution:
    def trap(self, height: List[int]) -> int:
        sum = 0
        heightLen = len(height)
        for i in range(1, heightLen - 1):
            curHeight = height[i]
            # 初始高度设为 当前列的高度 向两边寻找更高的列
            maxLeft, maxRight = curHeight, curHeight
            for j in range(0, i):
                maxLeft = max(maxLeft, height[j])
            for j in range(i + 1, heightLen):
                maxRight = max(maxRight, height[j])
            sum += min(maxLeft, maxRight) - curHeight
        return sum
动态规划 预先处理好 元素i 及其左右两边的最大值 时间复杂度 O(N)
class Solution:
    def trap(self, height: List[int]) -> int:
        heightLen = len(height)
        # i 及其 左边的最大值 index 0 没有左边 最大值为本身 从左往右
        leftMax = [height[0]] + [0] * (heightLen - 1)
        # 同上 index len-1 没有右边 最大值为本身 从右往左
        rightMax = [0] * (heightLen - 1) + [height[-1]]
        for i in range(1, heightLen):
            # i及其左边的最大值 = max(i - 1 及其左边的最大值, i本身的值)
            leftMax[i] = max(leftMax[i - 1], height[i])
        for i in range(heightLen - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])
        return sum(min(leftMax[i], rightMax[i]) - height[i]  for i in range(1, heightLen - 1))
单调栈 时间复杂度O(N)
class Solution:
    def trap(self, height: List[int]) -> int:
        indexStack = []
        sum = 0
        for i in range(len(height)):
            while indexStack and height[i] > height[indexStack[-1]]:
                bottom = indexStack.pop()
                # 如果退栈之后栈为空 则没有左边界 不会有积水
                if not indexStack:
                    break
                left = indexStack[-1]
                # 两墙之间的距离 * (两墙最小高度 - 弹出的底部的高度)
                sum += (i - left - 1) * (min(height[i], height[left]) - height[bottom])
            indexStack.append(i)
        return sum 
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/916055.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号