Алгоритм нахождения трех чисел в массиве такой, что a <b <c и v [a]

Question

Учитывая вектор целых чисел, мне нужно выяснить, существует ли три вектора a, b, c в векторе, таких как a < b< c и v[a] < v[c] < v[b].

Мой подход до сих пор был следующим.Во-первых, я забываю о a и нахожу для каждого числа в векторе минимум v [i], который находится слева от этого элемента.Я храню эту информацию в другом массиве.Затем я применяю сортировку слиянием, и когда я достигаю точки пересечения двух элементов, я проверяю, мог ли правый элемент быть c, а левый b.Однако мне также нужно проверить, могут ли другие элементы, которые пересекаются с правильным элементом, быть b, и это слишком сильно увеличивает временную сложность.Мне нужно, чтобы он был максимально линейным.Не могли бы вы дать мне подсказку о том, как действовать?

РЕДАКТИРОВАТЬ: Простите, название не было хорошо раньше.Мне нужно, чтобы a

EDIT2: Ограничение : я не могу использовать структуры данных, кроме векторов.И алгоритм должен быть основан на методе «разделяй и властвуй» .

Answer 1

Вы можете сделать это за O ( n ) времени и наихудшего случая O ( n ) дополнительного пространства, перебираямассив при сохранении стека (структура данных LIFO) максимальных запрещенных диапазонов (v[a], v[c]).Самый верхний элемент стека - это диапазон от наименьшего значения, видимого до этого, до наибольшего значения, наблюдаемого после этого наименьшего значения.(В качестве альтернативы по причинам реализации вам может оказаться проще хранить этот диапазон в отдельной переменной и использовать стек только для старых запрещенных диапазонов.)

Обработка любого отдельного элемента может занятьдо O ( n ) времени (если необходимо развернуть весь стек вплоть до самого первого диапазона), но эта стоимость обязательно амортизируется, так что обработка всегомассив все еще только O ( n ) времени (потому что единственная причина, по которой обработка элемента размотает весь стек, состоит в том, что он объединяет все запрещенные диапазоны в один гораздо больший, в этом случае ему не нужно повторно добавлять все диапазоны, которые он выдал, так что работа выполняется только один раз ).