LeetCode-904-水果成篮

一：题目描述：

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

二：示例与提示

示例 1:

1
2
3

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2:

1
2
3
4

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3:

1
2
3
4

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4:

1
2
3

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

三：思路

暴力求解法

• 两层循环遍历，找到所有情况

  • 外层循环控制起始位置
  • 内层循环控制终止位置
  • 两层嵌套，找到满足小于等于两种水果的所有情况，然后返回最大长度

• 该结果会超时

滑动窗口

• 当出现第三种水果时候，窗口应该缩小，直到满足还是小于等于两种水果的情况
• 当满足小于等于两种情况时候，窗口自动扩大，右指针向右移动
• 使用map数据结构来对水果进行存储

set数据结构不行

• set数据结构是无法实现的
  • 因为set集合只会存在不同的元素，相同的元素无法存储，也无法存储每个元素出现的次数
  • 无法记录该元素的次数，就无法正确地移动左指针，就无法正确的记录每个正常情况下的长度值

输入

1

[3,3,3,1,2,1,1,2,3,3,4]

• 使用set数据结构存储水果数量时候，可以看到右指针是正确移动的，但是左指针只移动了一次
• 虽然前三个案例是可以通过
• 但出现多个重复水果时候，就会由于集合中无法记录不同水果出现的次数，导致无法正确移动左指针
• 导致长度计算出现问题
• 正确应该当出现3,1,2情况时，left指针已经移动到了最后一个3，但他还是在第一个3，所以只能使用map数据结构来存储元素次数

四：代码 + 复杂度分析

暴力求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * @param {number[]} fruits
 * @return {number}
 */
var totalFruit = function(fruits) {
    //暴力求解
    if(fruits.length <= 2) return fruits.length
    let result = -Infinity
    for(let i = 0; i < fruits.length; i++) {
        let set = new Set()
        for(let j = i; j < fruits.length; j++) {
            set.add(fruits[j])
            if(set.size <= 2) {
                result = Math.max(result, j - i + 1)
            }else {
                break
            }
        }
    }
    return result
};

• 时间复杂度：O（n ^ 2）

• 空间复杂度：O（1）

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * @param {number[]} fruits
 * @return {number}
 */
var totalFruit = function(fruits) {
    //滑动窗口
    let left = 0
    let map = new Map()
    let result = -Infinity
    for(let right = 0; right < fruits.length; right++) {
        //利用map数据结构存储水果
        map.set(fruits[right], (map.get(fruits[right]) || 0) + 1);
        //遇到第三类水果缩小窗口
        while(map.size > 2) {
            //判断最左边水果的数量 如果为0直接删除 如果不为0 减一
            map.set(fruits[left], map.get(fruits[left]) - 1)
            if(map.get(fruits[left]) == 0) {
                map.delete(fruits[left])
            }
            //移动左指针
            left++
        }
        //记录
        result = Math.max(result, right - left + 1)
        console.log(result)
    }
    // console.log(map)
    return result
};

• 时间复杂度：O（n）
  • 外层循环从 right = 0 遍历到 right = n - 1，其中 n 是输入数组 fruits 的长度。这一步的时间复杂度是 O(n)
  • 内层循环是一个 while 循环，它会在窗口中水果种类数大于2时缩小窗口。在最坏情况下，内层循环会将窗口从右到左移动，因此最多会遍历一次整个数组。因此，内层循环的时间复杂度也是 O(n)
  • 整体算法复杂度不是O（n ^ 2），因为这是因为这两个循环并不会同时遍历整个数组的所有元素，内层循环当满足条件小于等于2时候，内层while循环就不执行，一旦窗口中的水果种类数恢复到2以下，就会退出内层循环，内层 while 循环的最坏的时间复杂度也是 O(n)，但它并不会导致整体的算法复杂度为 O(n^2)
• 空间复杂度：O（1）