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

leetcode 1642. 可以到达的最远建筑python

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

leetcode 1642. 可以到达的最远建筑python

题目描述:

题解:

思路:先全部使用梯子,如果梯子不够用了,则将高度差最短的位置换为砖头。

1.设置一个最小堆gaps记录两个相邻位置的高度差。

2.从下标为0的位置开始,如果当前位置高于或等于下一个位置,则直接下移到下一个位置,否则计算两个位置之间的高度差加入gaps。

3.如果gaps中元素的数量大于ladders,说明此时梯子已经用完,从gaps中取出一个最小值,替换为砖头,如果砖头也被用完,则返回当前位置。

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        n = len(heights)
        gaps = []
        heapq.heapify(gaps)
        for i in range(n-1):
            if heights[i+1]>heights[i]:
                heapq.heappush(gaps,heights[i+1]-heights[i])
                if len(gaps)>ladders:
                    bricks = bricks-heapq.heappop(gaps)
                    if bricks<0:
                        return i
        return n-1

 

 

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/666052.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

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

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