本次刷题日记的第 57 篇,力扣题为:875. 爱吃香蕉的珂珂,中等
一、题目描述:
差点看成爱吃香蕉的呵呵,额,加班加傻了吧。
看看吃香蕉的题,我们会不会很容易就会有思路
二、这道题考察了什么思想?你的思路是什么?
仔细看看珂珂是如何在 h 小时内,还要用最慢的速度吃掉香蕉的:
- 题目给出有多堆香蕉,用数组来表示每一堆香蕉里面香蕉的具体个数
- 还给出了要求我们在 h 小时内将香蕉全部吃完
- 题目要求不仅我们要在 h 小时内吃完,还要我们用最慢的速度吃完,也就是咱们吃完香蕉消耗的时间要无限趋近于 h 小时
分析
仔细看了一下,珂珂喜欢慢慢吃,感觉就是玩心跳呀,无限趋近于警卫回来的时间,这不是很容易被抓住吗,哈哈哈,不过我们无需考虑这个事情,专注吃香蕉就可以了
我们来分析一波,在这 n 堆香蕉里面,珂珂吃香蕉的速度必然是每小时至少 吃 1 根香蕉,另外最多也是每小时吃掉这一堆香蕉里面的最大的一堆
特别注意,这里是不能在同一个小时吃掉 2 堆香蕉内的某几根
那么,看到这里,我们就能够明白,珂珂吃掉香蕉的速度肯定是在 1-- max ( max 为数量最多的一堆香蕉) 之间
例如,一堆香蕉有 num 个,假如珂珂现在吃香蕉的速度为每小时 m 个,这个时候,珂珂吃掉这一堆香蕉就需要花 num/m 的时间 对吗?
其实不对,比如 num = 9,m = 5 ,这个时候 9/5 = 1 的,因此我们还需要考虑到剩下的 4 根香蕉,珂珂也是要耗时 1 个小时的,因此,我们可以这样来计算
(num + m -1) /m 就可以满足我们的要求
再接着分析,咱们这就回到了查找算法了,也就是咱们子啊 1 -- max 中找到一个合适的速度 k,令其满足能够在 h 小时内吃完所有香蕉,且这个 k 还是最小的
因此,综合上述,咱们就有这样的思路
- 找到数组中最大值
- 通过二分法的方式,查找1 -- max 中合适的数据
三、编码
根据上述逻辑和分析,我们就可以翻译成如下代码
需要注意,通过二分的方式查找数据的时候,若指定到某个值 x,计算出来的时间小于 h,咱们就需要继续找,直到找到那个最后一个小于等于 h 的 x
编码如下:
func minEatingSpeed(piles []int, h int) int { left, right := 1, max(piles) // 定义一个帮助函数,用于计算咱们吃掉所有香蕉要花的时间 helper := func(num int) bool { s := 0 for _, p := range piles { s += (p + num - 1) / num } return s <= h } for left < right { mid := (left + right) / 2 if helper(mid) { right = mid } else { left = mid + 1 } } return left } func max(nums []int) int { ans := nums[0] for _, num := range nums { if num > res{ res= num } } return res }
四、总结:
就这么看来,时间复杂度是 O(nlogm) ,谈到二分法,这里就比较明确了,时间复杂度是 O(logn) 再套上咱们还需要遍历整个数组中的值,因此时间复杂度是 O(nlogm)
空间复杂度是 O(1) ,这个更加明确了,我们本次没有引入多余的空间消耗
原题地址:875. 爱吃香蕉的珂珂
今天就到这里,学习所得,若有偏差,还请斧正
欢迎点赞,关注,收藏
朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力
好了,本次就到这里
技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。
我是阿兵云原生,欢迎点赞关注收藏,下次见~