前言
滑动窗口之前已经写过几篇笔记了,懂了滑动窗口的套路,以后就可以就着这个模板进行更改了,
今天这一道题,可能一下子并不能想到使用滑动窗口来做,但接着分析一下,其实发现非常符合滑动窗口思想,
如果想了解解决滑动窗口问题的套路,可以参考一下我这两篇笔记,大家一起学习交流,如果有错希望大佬不吝赐教!
LeetCode学习笔记——最长子串(Sliding Window)
LeetCode学习笔记——最小覆盖串/字母异位词(Sliding Window)
水果成篮
在一排树中,第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始,然后重复执行以下步骤:
- 把这棵树上的水果放进你的篮子里。如果你做不到,就停下来。
- 移动到当前树右侧的下一棵树。如果右边没有树,就停下来。
请注意,在选择一颗树后,你没有任何选择:你必须执行步骤 1,然后执行步骤 2,然后返回步骤 1,然后执行步骤 2,依此类推,直至停止。
你有两个篮子,每个篮子可以携带任何数量的水果,但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果总量是多少?
示例 1:
1 | 输入:[1,2,1] |
示例 2:
1 | 输入:[0,1,2,2] |
示例 3:
1 | 输入:[1,2,3,2,2] |
示例 4:
1 | 输入:[3,3,3,1,2,1,1,2,3,3,4] |
解题思路
这道题题目一看上去确实让人有点懵,其实他的意思是,
给定一个数组,数组中存在着不同值的数字,每种数字代表一种类型的水果,注意,这里是类型,不是数量,比如tree[i] = {1, 2}, 1 代表 1 型水果,2代表2型 水果,数组中数字的频率代表该类型水果的数量,仅此而已。水果类型的数量和某种水果类型的数量,这两者需要分清。
可以从数组任何位置出发,且只能往右边走,每走过一棵树,就把水果放进篮子,你只有两个篮子,也就是最多只能装两种类型的水果,当你走到第三种类型的水果或者走到数组末尾时,就要停下来,求从哪里开始能装最多的水果。
为什么说这道题符合滑动窗口的思想呢?因为其实在搜索的过程中,就是一个变动窗口,窗口的左边界就是开始的位置,右边界就是到达了临界条件。
临界条件是什么?
- 当遇到第三种类型的水果
- 当到达数组末尾
此时右边界减去左边界,就是水果的总量。
滑动窗口一般配合哈希表来做,哈希表用来记录窗口中出现的每种类型水果的数量(也就是每种数字的频率)。
我们需要两个指针 left 和 right 作为窗口的边界,用哈希表 window 来记录窗口中的水果类型及其数量,用 count 来记录窗口中水果类型数量,maxlen 为窗口的最大长度,将作为结果返回。
一开始,窗口的大小为 0, left 和 right 都指向数组首位,window 将right 指向的水果类型记录下来,
right 移动,window 继续记录,如果之前window 中存在该类型的水果,就在原来的基础上增加,
right 继续移动,window 继续记录,当前窗口中水果的类型为 [1, 2], 所以count为2,因为窗口中水果的类型达到了2,为最大类型数量,此时可以更新窗口长度,
right 继续移动,此时窗口内水果类型的数量仍然为 2,则窗口的长度需要更新,
当right继续移动,此时遇到第三种类型的水果,但因为窗口中水果类型数量已经达到最大,那么这个类型的水果不能被装进窗口,但window会将其记录下来,此时需要移动左边界 left 缩小窗口,
移动左边界的目的是为了寻找新的窗口,寻找新的窗口的前提,是要将窗口恢复到具有可扩大的状态,条件就是要窗口的水果类型小于等于 2,移动左边界,直到原窗口中的某一种类型的水果的数量为 0,则说明该窗口中没有这种类型的水果了,
此时新窗口开始了,将新窗口的长度和 maxlen 进行比较,如果更大,则更新窗口。
直到 right 到达数组末尾前,以上过程都将继续。
经过以上过程,如果能够理解,应该已经可以把这道题敲下来了,接下来总结一下伪代码,以便能把上面的过程转换成代码。
1 | # tree[] |
接下来就是转成代码了,有一个地方需要注意的是,在缩小窗口的时候,某种类型的水果的数量会减为0,但不代表该 Key 值被移除哈希表,所以在窗口扩大的时候,对right所指的水果类型进行判断时,要多判断其是否在window中为0的情况,如果为0,也看作是一种新类型的水果。
代码
1 | class Solution { |