Постановка задачи(официальная)
Вы посещаете ферму, на которой деревья выстроены в один ряд слева направо. Деревья представлены целочисленным массивом fruits
, где fruits[i]
— это тип фруктов на i-ом дереве.
Вы хотите собрать как можно больше фруктов, но владелец фермы установил следующие правила:
-
У вас есть две корзины, каждая из которых может содержать только один тип фруктов.
-
В каждой корзине может быть неограниченное количество фруктов.
-
Начиная с любого дерева, вы должны собирать фрукты с каждого дерева (включая стартовое), двигаясь вправо.
-
Если вы встречаете дерево, фрукты которого не могут поместиться в ваши корзины, вы должны остановиться.
Задача состоит в том, чтобы найти максимальное количество фруктов, которые можно собрать, соблюдая эти правила.
Упрощенная версия постановки
Дан массив fruits
, где каждый элемент представляет дерево, а его значение указывает тип фрукта, который растет на этом дереве. У нас есть две корзины, каждая из которых может содержать неограниченное количество фруктов одного типа(к примеру, в одну корзину можем положить все фрукты типа 4, а во вторую корзину положить все фрукты типа 7). Наша цель — собрать как можно больше фруктов, непрерывно двигаясь слева направо от любого начального дерева, пока не встретим тип фрукта, который не помещается в корзины(к примеру, в одной корзине фрукты типа 4, в другой корзине фрукты типа 7, а сейчас мы рядом с деревом на котором растет фрукт типа 2, мы не можем добавить этот тип ни в одну корзину, т.к. в корзине может находиться фрукты только одного типа).
Подход к решению
Для решения задачи мы будем использовать технику «скользящего окна» (sliding window) и хэш-таблицу для отслеживания количества каждого типа фруктов в текущем окне.
Почему именно этот подход?
-
Эффективность: Метод скользящего окна позволяет пройти по массиву всего один раз, что обеспечивает линейную временную сложность O(n). Это оптимально для больших массивов.
-
Отслеживание состояния: Хеш-таблица помогает быстро проверять и обновлять количество типов фруктов в текущем окне.
-
Гибкость: С помощью сдвига границ окна можно динамически адаптироваться к изменениям типов фруктов и корректировать размер окна.
Алгоритм
-
Инициализация переменных:
-
res
для хранения результата (максимальное количество фруктов). -
type_counter
для отслеживания количества каждого типа фруктов в текущем окне. -
left
для обозначения левой границы окна.
-
-
Проход по массиву
fruits
:-
Используем переменную
right
для обозначения правой границы окна. -
Увеличиваем счетчик для текущего типа фрукта
right_fruit
.
-
-
Проверка условия допустимости окна:
-
Если количество типов фруктов в окне становится больше двух (
len(type_counter) == 3
), сдвигаем левую границу окнаleft
вправо, уменьшая счетчики для фруктов и удаляя типы фруктов с нулевым счетчиком.
-
-
Обновление результата:
-
На каждой итерации обновляем
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 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 res = max(res, right - left + 1) return res
Объяснение кода
-
Инициализация:
-
res
— переменная для хранения максимального количества фруктов. -
type_counter
— хэш-таблица для отслеживания количества каждого типа фруктов в текущем окне. -
left
— индекс левой границы окна.
-
-
Основной цикл:
-
Проходим по массиву
fruits
с правой границей окнаright
. -
Увеличиваем счетчик для текущего типа фрукта
right_fruit
.
-
-
Уменьшение окна:
-
Если количество типов фруктов в окне превышает два (
len(type_counter) == 3
), сдвигаем левую границу окна вправо до тех пор, пока количество типов фруктов не станет допустимым (два или меньше).
-
-
Обновление результата:
-
На каждой итерации обновляем
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).
ссылка на оригинал статьи https://habr.com/ru/articles/831882/
Добавить комментарий