建设论坛网站大全,工作,中英文企业网站制作,上海单位名称大全题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer#xff08;专项突击版#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
狒狒喜欢吃香蕉。这里有 N 堆香蕉#xff0c;第 i 堆中有 piles… 题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer专项突击版系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
狒狒喜欢吃香蕉。这里有 N 堆香蕉第 i 堆中有 piles[i] 根香蕉。警卫已经离开了将在 H 小时后回来。
狒狒可以决定她吃香蕉的速度 K 单位根/小时。每个小时她将会选择一堆香蕉从中吃掉 K 根。如果这堆香蕉少于 K 根她将吃掉这堆的所有香蕉然后这一小时内不会再吃更多的香蕉下一个小时才会开始吃另一堆的香蕉。
狒狒喜欢慢慢吃但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 KK 为整数。
示例 1
输入: piles [3,6,7,11], H 8输出: 4
示例 2
输入: piles [30,11,23,4,20], H 5输出: 30
示例 3
输入: piles [30,11,23,4,20], H 6输出: 23
提示
1 piles.length 10^4piles.length H 10^91 piles[i] 10^9
题目思考
如何优化时间复杂度?
解决方案
思路
分析题目, 最容易想到的思路就是从速度 1 开始遍历, 基于当前速度计算吃完所有香蕉的时间, 如果小于 h 就直接返回不过这样时间复杂度达到了 O(NM), 其中 N 是香蕉堆数, M 是速度上限, 即所有堆的最大香蕉根数 (没必要使用更大的速度, 因为每次只能吃一堆)根据题目规模, 这种做法肯定会超时, 如何优化呢?不难发现, 当速度增大时, 吃完香蕉的时间一定是递减的, 这里存在单调性我们可以利用这一点, 采用二分查找的方式加速也就是基于速度上下限 1 和 M, 二分查找满足要求的最小速度: 如果当前速度不满足要求, 则向右半区间查找; 否则更新最终结果为较小值, 并向左半区间查找而判断某个速度是否满足要求也很简单: 直接遍历所有堆, 累加每一堆按照当前速度吃完所需的时间, 如果时间总和不超过 h, 则满足要求, 否则不满足要求最后, 遍历完整个区间后的最终结果即为满足要求的最小速度下面代码中有详细的注释, 方便大家理解
复杂度
时间复杂度 O(NlogM): N 是香蕉的堆数, M 是所有堆的最大香蕉根数, 需要在区间[1,M]之间进行二分查找 (O(logM)), 而判断当前速度是否有效, 需要遍历整个堆 (O(N)), 所以整体时间复杂度就是 O(NlogM)空间复杂度 O(1): 只使用了几个常数空间的变量
代码
class Solution:def minEatingSpeed(self, piles: List[int], h: int) - int:# 二分查找有效性判断# 最小速度是1, 最大速度是所有堆的最大香蕉根数# 没必要使用更大的速度, 因为每次只能吃一堆s, e 1, max(piles)res edef isValid(speed):# 判断使用当前速度吃香蕉时, 能否在h小时内吃完hour 0for p in piles:# 当前堆需要吃ceil(p/speed)小时hour math.ceil(p / speed)if hour h:# 总时间超过了h, 无效return False# 可以在h小时内吃完return True# 二分查找满足要求的最小速度while s e:m (s e) 1if isValid(m):# 当前速度有效, 更新res为两者较小值res min(res, m)# 然后向左查找, 检查是否存在更小的有效速度e m - 1else:# 当前速度无效, 只能向右查找s m 1return res大家可以在下面这些地方找到我~ 我的 GitHub 我的 Leetcode 我的 CSDN 我的知乎专栏 我的头条号 我的牛客网博客 我的公众号: 算法精选, 欢迎大家扫码关注~
