Я считаю, что следующий алгоритм выполняется за O (n) времени и дает оптимальное решение.Это немного сложно, поэтому я разделю логику на два случая: один, в котором мы рассмотрим случай, когда в массиве нет повторяющихся значений, и один, в котором мы рассмотрели случай, когда допустимы дубликаты.
Ключевой структурой данных, которую мы будем использовать, является декартово дерево , представляющее собой максимальную кучу, построенную из диапазона данных со свойством, которое при обходе узлов дерева создаетЗначения последовательности в том порядке, в котором они появляются.Критическая деталь заключается в том, что можно построить декартово дерево для последовательности элементов за O (n) времени.
В качестве примера, учитывая последовательность 4 1 0 3 2, мы получили бы это декартовое дерево:
4
\
3
/ \
1 2
\
0
Обратите внимание, что обход inorder действительно возвращает 4 1 0 3 2.
Теперь я утверждаю, что конечные точки диапазона, который мы ищем, должны быть родителем / потомкомпара в декартовом дереве (то есть, либо первый узел является родителем второго узла, либо наоборот).Обратите внимание, что мы не ищем узел и какого-либо предка, а конкретно пару родитель / потомок.Чтобы доказать это, я докажу следующие два утверждения:
Требование 1 : Любая пара родитель / потомок в декартовом дереве определяет диапазон значений в исходной последовательности, который не имеет никакого посредниказначения, превышающие конечные точки.
Заявка 2 : Любой диапазон значений в последовательности, который не имеет промежуточных значений, превышающих его конечные точки, должен иметь эти конечные точки в качестве пары родительский / дочерний вДекартово дерево.
Взятые вместе, они все вместе доказывают, что диапазон, который мы ищем, должен быть парой родитель / потомок в декартовом дереве.Это тогда дает нам простой алгоритм линейного времени для решения задачи, когда все значения различны.Во-первых, за O (n) время построим декартово дерево для диапазона.Затем, рекурсивно исследуйте дерево, и для каждой пары родительский / дочерний найдите расстояние между этими парами, беря самый большой диапазон, который мы находим.Этот второй шаг также выполняется в O (n), поскольку декартово дерево - это двоичное дерево, и поэтому число ребер равно O (n).
Доказательство первого утверждения: Родитель/ дочерняя пара должна выглядеть как
u
\
v
/ \
A B
или
u
/
v
/ \
A B
Напомним, что декартово дерево хранит свои элементы таким образом, что обход по порядку элементов дерева дает элементымассива, используемого для создания дерева в том порядке, в котором они появляются в массиве.Это означает, что в случае (1) мы рассматриваем диапазон элементов, начиная с u, содержащий все A и заканчивая b.Точно так же в случае (2) диапазон начинается с v, затем содержит все B, а затем заканчивается u.Мы докажем утверждение, что u и v не имеют промежуточных значений, которые больше, чем u или v, в силу противоречия.Предположим, что это так, и значение w больше, чем u или v. По определению декартового дерева, если w находится между u и v в исходной последовательности, то в случае (1) оно должно быть вподдерево A и в случае (2) оно должно быть в поддереве B. Но декартово дерево - это максимальная куча, и поэтому в случае (1) и u, и v больше, чем все в A, а в случае (2) обаu и v больше, чем все в B, противоречие.Таким образом, диапазон значений между любой парой родитель / потомок должен быть не больше, чем родитель или потомок.
Доказательство утверждения 2: По противопоказанию;мы покажем, что если есть подпоследовательность исходного массива, начинающаяся с u и заканчивающаяся v, которая содержит элемент больше, чем u или v, то u и v не могут быть родительской / дочерней или дочерней / родительской парой в декартовом дереве,Доказательство практически идентично приведенному выше - если бы u и v были парой родитель / потомок, то в случае (1) выше w должно быть в A, а в случае (2) w должно быть в B, в обоих случаяхнарушая тот факт, что декартово дерево является максимальной кучей.
Приведенные выше доказательства показывают нам, что если все значения различны, мы можем решить эту проблему за линейное время, просто построив декартово дерево и выполнив простую прогулку по дереву. Но что произойдет, если элементам разрешено быть дубликатами, как в исходной постановке задачи? В этом случае мы можем использовать модифицированную декартову древовидную структуру. Мы позволим объединить узлы в «метаноду» из нескольких различных значений декартовых деревьев, которые имеют одинаковое значение. Например, последовательность 2 7 1 7 8 0 3 8 2 будет выглядеть следующим образом:
[8 ------- 8]
/ \ \
/ 3 2
/ /
/ 0
/
[7 -- 7]
/ \
2 1
Здесь корень представляет собой метанод, состоящий из двух узлов со значением 8, а первый 8-метанод состоит из двух 7 метанодов.
В целях обозначения пусть «самым левым» узлом метаноды будет узел, самый дальний слева в метаноде, и пусть «самым правым» узлом метаноды будет узел, самый дальний вправо в метаноде.
В этом модифицированном декартовом дереве мы можем определить обход по узлам как узел, который посещает все узлы в метаноде в порядке слева направо, выполняя обход по каждому из содержащихся в нем узлов. Затем мы следим за тем, чтобы модифицированное декартовое дерево строгого max-heap (каждый узел должен быть строго больше, чем любой из его дочерних элементов) и что обход по дереву по порядку следования возвращает значения в том же порядке, в котором появляются в исходной последовательности.
Обратите внимание, что эта обобщенная конструкция содержит наше исходное решение в качестве особого случая - если все значения различны, в этой древовидной структуре нет ничего различного. Я также утверждаю без доказательства, что можно построить одну из этих структур в O (n) путем прямой модификации стандартного алгоритма декартового дерева.
В этой измененной древовидной структуре диапазон значений без промежуточных значений, по крайней мере равных конечным точкам, соответствует:
- Родитель и самый правый узел его левого потомка.
- Родитель и самый левый узел его правого потомка.
- Два соседних узла в одном и том же метаноде.
Доказательство первых двух утверждений в значительной степени является прямой модификацией доказательства для приведенного выше случая. Разница в том, что вместо доказательства противоречия о том, что он нарушит свойство max-heap, вместо этого вы бы заявили, что оно нарушает свойство strong max-heap. Вы также сказали бы, что любые равные значения в середине диапазона должны проявляться как узлы, которые не позволят конечным точкам диапазона быть самыми левыми или самыми правыми узлами в метаноде. Доказательством третьего утверждения является (примерно) то, что любые узлы между двумя узлами должны быть строго меньше, чем конечные точки, и если бы в середине было равное значение, то эти два узла не были бы смежными метанодами.
Учитывая это наблюдение, мы можем решить исходную задачу за O (n) времени следующим образом. Сначала создайте обобщенное декартово дерево из входного диапазона. Затем, пройдитесь по дереву и посмотрите на все указанные пары элементов, которые могут быть диапазоном, выбирая самый большой из найденных. Поскольку для каждого узла необходимо проверять только постоянное число других узлов (его родитель, левый и правый братья и сестры, а потомки дают не более пяти узлов для проверки), это можно сделать за O (n) времени для чистой среды выполнения, равной О (п).
Уф! Это была огромная проблема. Я не знаю, является ли это идеальным решением, но это, по крайней мере, доказывает, что это можно сделать за O (n) раз. Если кто-то придумает лучший ответ, я бы хотел его увидеть.