Задача: 904. Fruit Into Baskets
Сложность: medium

Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.

Пример:

Input: fruits = [1,2,1]
Output: 3

👨‍💻 Алгоритм:

1⃣Использовать метод скользящего окна для поддержания текущего подмассива, содержащего не более двух типов фруктов.

2⃣Перемещать правый указатель, расширяя окно, и обновлять количество каждого типа фрукта в окне.
Если количество типов фруктов в окне превышает два, перемещать левый указатель, уменьшая окно, пока в окне снова не будет не более двух типов фруктов.

3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге.

😎 Решение:

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> basket;
        int left = 0;
        int maxFruits = 0;

        for (int right = 0; right < fruits.size(); ++right) {
            basket[fruits[right]]++;
            while (basket.size() > 2) {
                basket[fruits[left]]--;
                if (basket[fruits[left]] == 0) {
                    basket.erase(fruits[left]);
                }
                ++left;
            }
            maxFruits = max(maxFruits, right - left + 1);
        }

        return maxFruits;
    }
};

Ставь 👍 и забирай 📚 Базу знаний