Ищем максимальную разницу между соседями. User-friendly-разбор задачи по алгоритмам
Привет, Хабр!
Давайте поговорим про алгоритмы. Новички часто воспринимают их как что-то тяжёлое, сложное и непонятное, и отчасти это правда, но алгоритмы — это базис. А чем лучше вы знаете базис своей специальности, тем с большей вероятностью преуспеете в ней.
Сегодня мы посмотрим на одну красивую задачу по алгоритмам. Не будем отпугивать людей от работы с алгоритмами на самом старте, поэтому в нашем разборе не будет ни развесистых деревьев отрезков, ни разномастных оптимизаций задачи о рюкзаке, ни вероятностных тестов на простоту. User-friendly algos.
Вот задача: найти максимальную разницу между соседями.
Дан массив из N целых чисел. Он никак не упорядочен, а числа могут повторяться. Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов. Необходимо найти максимальную такую разницу и сделать это наиболее оптимальным способом.
Сложно? Можете попробовать сделать это до того, как нажмёте «Читать дальше», а потом проверим решение.
Итак, поехали. Максимальная разница между соседями.
Рассмотрим пример:
Пусть дан массив из N=11 элементов.
A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]
Cначала решим задачу наивно, это часто помогает. Мы можем сделать именно то, что от нас требует условие задачи — отсортировать числа и найти разницу между соседними элементами. В зависимости от того, какую сортировку мы будем использовать, сложность решения будет варьироваться.
Если используем qsort или mergesort, то временная сложность составит O (N log N). Если нам известно, что числа распределены достаточно плотно на множестве целых чисел, то можно использовать сортировку подсчётом. Тогда мы получим O (U + N), где U — разность между максимальным и минимальным элементом. Случай относительно редкий, но стоит помнить про такую возможность.
После сортировки получим массив:
As = [-3, -2, -1, 3, 4, 10, 10, 15, 20, 21, 22]
Выпишем массив разностей: D = [1, 1, 4, 1, 6, 0, 5, 5, 1, 1]
Получаем, что максимальная разница составляет 6.
Теперь подумаем, можно ли решить задачу быстрее? При переборе пар соседних элементов мы будем рассматривать много пар с маленькой разностью. Такие пары, возможно, и не смогут никогда дать наибольшую разность. И действительно, в отсортированном массиве у нас есть N-1 пара соседних чисел, разность между максимумом и минимумом пусть равна U. Тогда у наибольшей разности значение должно быть хотя бы U / (N — 1). Эта оценка верна по принципу Дирихле.
Если голуби рассажены в клетки, причём число голубей больше числа клеток, то хотя бы в одной из клеток находится более одного голубя.
9 клеток содержат 10 голубей, по принципу Дирихле, хотя бы в одной клетке находятся более одного голубя (Википедия)
Пусть D[1] = As[2] — As[1], … D[n — 1] = As[n] — As[n — 1], As[i] — i-й элемент отсортированного массива. Тогда D[i] >= 0, D[1] + … + D[N-1] = U.
Если предположить, что максимум из всех D[i] меньше U/(N-1), то вся сумма D[1] + … + D[N-1] будет строго меньше U — противоречие.
Отлично, мы получили нижнюю оценку на максимальную разность! Теперь попробуем как-то локализовать слишком близкие друг к другу элементы — разобьём отрезок от минимального до максимального элемента на полуинтервалы длиной L=U/(N-1). Каждый элемент попадёт ровно в один полуинтервал. Получим разбиение всех элементов на непересекающиеся группы, их ещё называют батчами.
Определить, в какой именно из них попал элемент x, очень просто — надо вычислить 1 + int ((x — a_min) / L) (нумеруем с единицы), где a_min — минимальный элемент в массиве A, его можно найти за один проход по исходному массиву. Исключение составит только максимальный элемент — элементы с таким значением лучше сделать отдельным батчом.
На рисунке представлено распределение из описанного выше примера. Для ясности проделаем эту процедуру руками:
U = 22 — (-3) = 25, N = 11 => L = 25/(11–1) = 2.5
A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]
(-1 — (-3)) / 2.5 = 0.8 => batch = 1
(-3 — (-3)) / 2.5 = 0 => batch = 1
(10 — (-3)) / 2.5 = 13/2.5 = 5.2 =>batch = 6
(20 — (-3)) / 2.5 = 23/2.5 = 9.2 => batch = 10
(21 — (-3)) / 2.5 = 24/2.5 = 9.6 => batch = 10
(4 — (-3)) / 2.5 = 7/2.5 = 2.8 => batch = 3
(3 — (-3)) / 2.5 = 6/2.5 = 2.4 => batch = 3
(22 — (-3)) / 2.5 = 10 => batch = 11
(10 — (-3)) / 2.5 = 5.2 => batch = 6
(-2 — (-3)) / 2.5 = 0.4 => batch = 1
(15 — (-3)) / 2.5 = 7.2 => batch = 8
Распределение по батчам выполняется за линейное время и требует O (n) дополнительной памяти. Обратите внимание, что элементы из одного батча не могут дать максимальную разницу между двумя элементами. Мы специально подобрали его размер таким образом.
Где могут находиться два соседних по значениям элемента? Конечно же, в соседних непустых батчах! Например, на рисунке элементы из третьего и шестого батча могут идти подряд в отсортированном массиве, так как батчи между ними пустые. Понятно, что соседними будут только два элемента — максимум из 3-го батча и минимум из 6-го. Аналогично, кандидатами на пару с максимальной разностью будут максимальный элемент первого батча и минимальный элемент третьего.
Выпишем все возможные пары элементов, которые могут дать наибольшую разность. Обозначим как min (i) — минимальный элемент в i-й группе, как max (i) — максимальный элемент.
max (1) = -1 min (3) = 3
max (3) = 4 min (6) = 10
max (6) = 10 min (8) = 15
max (8) = 15 min (10) = 20
max (10) = 21 min (11) = 22
Мы определили пары, которые стоит рассматривать. На практике необходимо сделать один проход по всем батчам, поддерживать последний непустой батч и максимальное значение в нём. Когда мы наткнёмся на следующий непустой батч, то найдём в нём минимум и попробуем обновить ответ.
Порадуемся — мы решили задачу за время O (N).
На самом деле, мы использовали достаточно известную идею и по сути проделали первые шаги карманной сортировки, в оригинале её называют bucket-sort.
Элементы раскладываются по корзинам, а потом элементы в каждой корзине сортируются
В худшем случае она работает за O (n^2), но среднее время работы при достаточном количестве батчей и равномерном распределении элементов составляет O (n).
«Но постойте, а как же случай, когда U=0, почему вы не рассмотрели его?», — спросит внимательный читатель. Этот случай вырожденный, вот мы его и не рассмотрели, но давайте сделаем это сейчас для полноты вариантов.
Если разница между минимумом и максимумом равно нулю, то максимальная разница тоже равна нулю. Собственно, это всё.
