904. 水果成篮

题目链接：https://leetcode.cn/problems/fruit-into-baskets/

代码

/**
 * 904. 水果成篮
 * https://leetcode.cn/problems/fruit-into-baskets/
 */

function totalFruit(fruits: number[]): number {
    let res = 0;
    let left = 0;
    const map = new Map<number, number>();
    for (let i = 0; i < fruits.length; i++) {
        map.set(fruits[i], (map.get(fruits[i]) || 0) + 1);
        while (map.size > 2) {
            const fruit = map.get(fruits[left])!;
            fruit === 1 ? map.delete(fruits[left]) : map.set(fruits[left], fruit - 1);
            left++;
        }
        res = Math.max(res, i - left + 1);
    }
    return res;
}

思路

使用滑动窗口 + Map：

• 用 Map 记录当前窗口内每种水果的数量；
• 右指针向右移动，将当前水果加入窗口；
• 当 Map 的大小超过 2 时（即窗口内水果种类超过 2 种），移动左指针缩小窗口，直到窗口内只有 2 种水果；
• 每次更新窗口长度的最大值。

时间复杂度 $O(n)$，空间复杂度 $O(1)$（最多存储 2 种水果的信息），其中 $n$ 为数组长度。