5248. Две корзины для фруктов
Medium
2 решили
В ряд стоят деревья.
Сбор такой: выберите любое стартовое дерево и дальше идите только вправо, снимая плод с каждого дерева на пути. Пропускать дерево нельзя. Как только на пути появляется третий вид, этот проход заканчивается — третий вид класть некуда.
Нужно набрать как можно больше фруктов за один такой проход. Верните это количество (это длина самого длинного непрерывного отрезка массива, в котором не больше двух разных чисел).
Подпоследовательность не подходит: деревья должны идти подряд, без дыр. При
fruits[i] — вид фрукта на дереве i. У вас две корзины: в каждой можно класть только один вид (сколько угодно штук этого вида). Одну корзину можно не использовать — собирать один вид тоже можно.Сбор такой: выберите любое стартовое дерево и дальше идите только вправо, снимая плод с каждого дерева на пути. Пропускать дерево нельзя. Как только на пути появляется третий вид, этот проход заканчивается — третий вид класть некуда.
Нужно набрать как можно больше фруктов за один такой проход. Верните это количество (это длина самого длинного непрерывного отрезка массива, в котором не больше двух разных чисел).
Подпоследовательность не подходит: деревья должны идти подряд, без дыр. При
n до 10^5 перебор всех отрезков за квадрат не уложится во время.fruits = [1, 2, 3, 2, 2]
индекс 0 1 2 3 4
вид 1 2 3 2 2
старт с 0: 1 2 | 3 … третий вид, длина 2
старт с 1: 2 3 2 2 виды {2,3}, длина 4 ← ответ
старт с 2: 3 2 2 виды {3,2}, длина 3Отрезок [3, 2, 2] тоже из двух видов, но он короче. Максимум даёт только [2, 3, 2, 2] → 4.Примеры:
Вход:
[1, 2, 1]
Выход:
3
Объяснение: Во всём массиве только виды 1 и 2, обе корзины заняты ими. Можно пройти все три дерева → 3.
Вход:
[0, 1, 2, 2]
Выход:
3
Объяснение: Весь массив нельзя: там три вида. Слева [0, 1] — длина 2. Справа [1, 2, 2] — виды {1, 2}, длина 3. Это лучший проход → 3.
Вход:
[1, 2, 3, 2, 2]
Выход:
4
Объяснение: Лучший проход — [2, 3, 2, 2] длины 4 (виды 2 и 3). Кусок [3, 2, 2] тоже из двух видов, но его длина только 3, это не ответ. Префикс [1, 2] даёт 2. Итого 4.
Вход:
[1, 0, 1, 4, 1, 4, 1, 2, 3]
Выход:
5
Объяснение: Лучший отрезок не с края, а в середине: [1, 4, 1, 4, 1] — пять деревьев и только виды 1 и 4. Слева [1, 0, 1] короче, справа после единицы сразу появляются 2 и 3. Ответ 5.
Ограничения:
1 <= fruits.length <= 10^5
0 <= fruits[i] <= 10^5
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!