Постановка задачи(официальная)

Ссылка на задачу: https://leetcode.com/problems/fruit-into-baskets

Вы посещаете ферму, на которой деревья выстроены в один ряд слева направо. Деревья представлены целочисленным массивом fruits, где fruits[i] — это тип фруктов на i-ом дереве.

Вы хотите собрать как можно больше фруктов, но владелец фермы установил следующие правила:

  1. У вас есть две корзины, каждая из которых может содержать только один тип фруктов.

  2. В каждой корзине может быть неограниченное количество фруктов.

  3. Начиная с любого дерева, вы должны собирать фрукты с каждого дерева (включая стартовое), двигаясь вправо.

  4. Если вы встречаете дерево, фрукты которого не могут поместиться в ваши корзины, вы должны остановиться.

Задача состоит в том, чтобы найти максимальное количество фруктов, которые можно собрать, соблюдая эти правила.

Упрощенная версия постановки

Дан массив fruits, где каждый элемент представляет дерево, а его значение указывает тип фрукта, который растет на этом дереве. У нас есть две корзины, каждая из которых может содержать неограниченное количество фруктов одного типа(к примеру, в одну корзину можем положить все фрукты типа 4, а во вторую корзину положить все фрукты типа 7). Наша цель — собрать как можно больше фруктов, непрерывно двигаясь слева направо от любого начального дерева, пока не встретим тип фрукта, который не помещается в корзины(к примеру, в одной корзине фрукты типа 4, в другой корзине фрукты типа 7, а сейчас мы рядом с деревом на котором растет фрукт типа 2, мы не можем добавить этот тип ни в одну корзину, т.к. в корзине может находиться фрукты только одного типа).

Подход к решению

Для решения задачи мы будем использовать технику "скользящего окна" (sliding window) и хэш-таблицу для отслеживания количества каждого типа фруктов в текущем окне.

Почему именно этот подход?

  1. Эффективность: Метод скользящего окна позволяет пройти по массиву всего один раз, что обеспечивает линейную временную сложность O(n). Это оптимально для больших массивов.

  2. Отслеживание состояния: Хеш-таблица помогает быстро проверять и обновлять количество типов фруктов в текущем окне.

  3. Гибкость: С помощью сдвига границ окна можно динамически адаптироваться к изменениям типов фруктов и корректировать размер окна.

Алгоритм

  1. Инициализация переменных:

    • res для хранения результата (максимальное количество фруктов).

    • type_counter для отслеживания количества каждого типа фруктов в текущем окне.

    • left для обозначения левой границы окна.

  2. Проход по массиву fruits:

    • Используем переменную right для обозначения правой границы окна.

    • Увеличиваем счетчик для текущего типа фрукта right_fruit.

  3. Проверка условия допустимости окна:

    • Если количество типов фруктов в окне становится больше двух (len(type_counter) == 3), сдвигаем левую границу окна left вправо, уменьшая счетчики для фруктов и удаляя типы фруктов с нулевым счетчиком.

  4. Обновление результата:

    • На каждой итерации обновляем res, вычисляя длину текущего окна.

Код решения

from collections import defaultdict
from typing import List

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        res = 0
        type_counter = defaultdict(int)
        left = 0  # левая граница окна

        for right in range(len(fruits)):  # правая граница окна
            right_fruit = fruits[right]
            type_counter[right_fruit] += 1

            # Когда в словаре становится 3 различных типа фруктов, сдвигаем левую границу окна
            # Это делается для того, чтобы в окне всегда было не больше 2 различных типов фруктов
            while len(type_counter) == 3:
                left_fruit = fruits[left]
                type_counter[left_fruit] -= 1
                if type_counter[left_fruit] == 0:
                    del type_counter[left_fruit]
                left += 1

            # Обновляем максимальную длину окна
            # Длина текущего окна равна (right - left + 1)
            res = max(res, right - left + 1)

        return res

Объяснение кода

  1. Инициализация:

    • res - переменная для хранения максимального количества фруктов.

    • type_counter - хэш-таблица для отслеживания количества каждого типа фруктов в текущем окне.

    • left - индекс левой границы окна.

  2. Основной цикл:

    • Проходим по массиву fruits с правой границей окна right.

    • Увеличиваем счетчик для текущего типа фрукта right_fruit.

  3. Уменьшение окна:

    • Если количество типов фруктов в окне превышает два (len(type_counter) == 3), сдвигаем левую границу окна вправо до тех пор, пока количество типов фруктов не станет допустимым (два или меньше).

  4. Обновление результата:

    • На каждой итерации обновляем res, вычисляя текущую длину окна (right - left + 1).

Визуализация решения

Рассмотрим массив fruits = [1, 2, 1, 2, 3, 3, 2, 1] и визуализируем шаги решения задачи, показывая текущее состояние скользящего окна.

Шаги выполнения:

Итерация 0:

  • Текущий фрукт: 1

  • Окно: [1], 2, 1, 2, 3, 3, 4, 1, 2

  • type_counter: {1: 1}

  • Длина окна: 1

Итерация 1:

  • Текущий фрукт: 2

  • Окно: [1, 2], 1, 2, 3, 3, 4, 1, 2

  • type_counter: {1: 1, 2: 1}

  • Длина окна: 2

Итерация 2:

  • Текущий фрукт: 1

  • Окно: [1, 2, 1], 2, 3, 3, 4, 1, 2

  • type_counter: {1: 2, 2: 1}

  • Длина окна: 3

Итерация 3:

  • Текущий фрукт: 2

  • Окно: [1, 2, 1, 2], 3, 3, 4, 1, 2

  • type_counter: {1: 2, 2: 2}

  • Длина окна: 4

Итерация 4:

  • Текущий фрукт: 3

  • Окно: [1, 2, 1, 2, 3], 3, 4, 1, 2

  • type_counter: {1: 2, 2: 2, 3: 1}

  • Длина окна: 5

  • Сокращение окна:

    • left: 1

    • Окно после сокращения: 1, [2, 1, 2, 3], 3, 4, 1, 2

    • type_counter: {1: 1, 2: 2, 3: 1}

    • Длина окна: 4

    • left: 2

    • Окно после сокращения: 1, 2, [1, 2, 3], 3, 4, 1, 2

    • type_counter: {1: 1, 2: 1, 3: 1}

    • Длина окна: 3

    • left: 3

    • Окно после сокращения: 1, 2, 1, [2, 3], 3, 4, 1, 2

    • type_counter: {2: 1, 3: 1}

    • Длина окна: 2

  • Окно после обновления результата: 1, 2, 1, [2, 3], 3, 4, 1, 2

  • Текущий максимум: 4

Итерация 5:

  • Текущий фрукт: 3

  • Окно: 1, 2, 1, [2, 3, 3], 4, 1, 2

  • type_counter: {2: 1, 3: 2}

  • Длина окна: 3

Итерация 6:

  • Текущий фрукт: 4

  • Окно: 1, 2, 1, [2, 3, 3, 4], 1, 2

  • type_counter: {2: 1, 3: 2, 4: 1}

  • Длина окна: 4

  • Сокращение окна:

    • left: 4

    • Окно после сокращения: 1, 2, 1, 2, [3, 3, 4], 1, 2

    • type_counter: {3: 2, 4: 1}

    • Длина окна: 3

  • Окно после обновления результата: 1, 2, 1, 2, [3, 3, 4], 1, 2

  • Текущий максимум: 4

Итерация 7:

  • Текущий фрукт: 1

  • Окно: 1, 2, 1, 2, [3, 3, 4, 1], 2

  • type_counter: {3: 2, 4: 1, 1: 1}

  • Длина окна: 4

  • Сокращение окна:

    • left: 5

    • Окно после сокращения: 1, 2, 1, 2, 3, [3, 4, 1], 2

    • type_counter: {3: 1, 4: 1, 1: 1}

    • Длина окна: 3

    • left: 6

    • Окно после сокращения: 1, 2, 1, 2, 3, 3, [4, 1], 2

    • type_counter: {4: 1, 1: 1}

    • Длина окна: 2

  • Окно после обновления результата: 1, 2, 1, 2, 3, 3, [4, 1], 2

  • Текущий максимум: 4

Итерация 8:

  • Текущий фрукт: 2

  • Окно: 1, 2, 1, 2, 3, 3, [4, 1, 2]

  • type_counter: {4: 1, 1: 1, 2: 1}

  • Длина окна: 3

  • Сокращение окна:

    • left: 7

    • Окно после сокращения: 1, 2, 1, 2, 3, 3, 4, [1, 2]

    • type_counter: {1: 1, 2: 1}

    • Длина окна: 2

  • Окно после обновления результата: 1, 2, 1, 2, 3, 3, 4, [1, 2]

  • Текущий максимум: 4

После всех итераций максимальное количество фруктов, которые можно собрать, равно 4.

Асимптотическая сложность

Сложность по времени: O(n)

  • Мы проходим по массиву fruits один раз с помощью правой границы окна (right).

  • В худшем случае левая граница окна (left) также проходит по каждому элементу массива один раз.

  • В результате, каждый элемент массива обрабатывается не более двух раз, что приводит к линейной временной сложности O(n), где n — длина массива fruits.

Сложность по памяти: O(1)

  • Мы используем хэш-таблицу type_counter для хранения количества каждого типа фруктов в текущем окне.

  • Максимальное количество различных типов фруктов в хэш-таблице ограничено двумя, так как у нас есть только две корзины.

  • Следовательно, количество памяти, необходимой для хранения данных в хэш-таблице, не зависит от размера входного массива и остается постоянным.

  • Это приводит к постоянной сложности по памяти O(1).