题目描述
这是 力扣上的 904. 水果成篮,难度为 中等。
题目分析
我们需要按照题目要求来采摘水果,看了题目描述和示例之后我们知道,我们咱们只有两个篮子,只能采摘两种类型的水果,数量没有上限,但是你以为你就可以肆无忌惮的采摘了吗?
题目要求我们可以从任意的树上开始摘,开始之后,咱们只能往右逐个树的去摘,最多两种类型,如果遇到了第三种类型,就要停止采摘了,那么问题其实就比较明确了,我们需要聚焦在,我们需要从哪棵树开始摘
思考:
对于一排树,我们需要知道从哪棵树开始采摘,我们采摘到的水果才是最大数量的,简单来说就是要找到这个期望的区间了,例如
找区间,我们可以使用滑动窗口来进行实现,咱们的窗口中,只能容纳两种类型的水果,水果数量一样也是无上限,如果超出第三种类型的水果在区间中,那么我们就要将第一种类型的水果从窗口种去掉
在窗口滑动的过程中,我们可以使用一个哈希表来记录哪些类型的水果在窗口中,key 为水果类型,value 为对应类型的水果数量
此处就要注意了,如果咱们遇到区间中有第三种类型的水果时,我们从哈希表中去除第一种类型的水果,直到这种类型的水果完全从区间去除掉才行,同时,我们需要将该种类型的 key 从 哈希表中去除掉
这样一来,我们遍历一遍 fruits 数组,每遍历一次我们就记录一下当前窗口种符合要求的水果数量,并取最大值即可
接下来,咱们就可以来实现编码了,咱们这次使用 golang 的方式来进行实现
Golang 的实现方式:
- 定义哈希表,golang 中就是 map
- 遍历 fruits 数组
- 符合要求的纳入滑动窗口
- 滑动窗口容纳不了的,就从窗口的头逐个去掉不符合要求的水果,同时去掉在 哈希表中 该中水果类型的 key
func totalFruit(fruits []int) int { help := make(map[int]int, 0) res := 0 // 定义双指针来实现滑动窗口 left := 0 for right,v := range fruits { help[v]++ for len(help) > 2 { // 此时说去 left -- right 区间已经有 3 种水果了,需要去掉第 1 种 tmp := fruits[left] help[tmp]-- if help[tmp] == 0{ delete(help, tmp) } left++ } res = max(res , right - left + 1) } return res } func max(a,b int) int { if a>b{ return a } return b }
这种实现方式,咱们的时间复杂度为 O(n),此处的 n 是 fruits 数组的长度,空间复杂度为 O(1),此处我们虽然开辟了 help 哈希表来进行处理,但是咱们的 help map 中最多只会有 3 个键值对,因此我们可以看做是常数级别的
今天就到这里,若有偏差,还请斧正
欢迎点赞,关注,收藏
朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力
好了,本次就到这里
技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。
我是阿兵云原生,欢迎点赞关注收藏,下次见~