Учитывая массив, могу ли я найти в O (n) самый длинный диапазон, конечные точки которого являются наибольшими значениями в диапазоне?

Ответ 1

Простое решение на основе стека. Итерации по массиву слева направо, с элементами хранения стека (технически, индексы, но используйте значения для сравнения):

• Самый большой слева (т.е. не больший или равный элемент между началом массива и элементом)
• Самый большой, начиная с предыдущего элемента в стеке.

При обработке следующего элемента x элементы pop, меньшие, чем x, если они относятся к категории 2 выше, затем нажмите x в стеке. Очевидно, вам нужно поддерживать текущий макс, чтобы он мог различать между категориями 2 и 1 в постоянное время.

Обработка выше - O (n) - каждый элемент может быть нажат не более одного раза и выталкивается не более одного раза. Имея последний стек, просто проверяйте соседние пары (в стеке) - одна из пар - это решение. Это тоже O (n).

Здесь изображение с тем, что должно оставаться в стеке (жирные прямоугольники) после всего сканирования массива:

(В приведенной выше картинке есть небольшая ошибка: четвертая полоса слева должна быть толстой или нарисованной короче первой, извините)

Почему это работает: последний стек содержит все элементы входного массива, которые не находятся между двумя более крупными элементами (я пропустил случай элемента между двумя равными элементами). Решение, очевидно, является соседней парой таких элементов.

Здесь реализация в Python:

from collections import namedtuple

E = namedtuple('E', 'i x')

def maxrange(iterable):
    stack = [E(0, None)]*2 # push sentinel values
    maxsofar = None

    top = lambda: stack[-1] # peek at the top element on the stack

    for i, x in enumerate(iterable):
        while top().x < x and top().x < maxsofar:
            stack.pop()
        stack.append(E(i, x)) # push
        maxsofar = max(maxsofar, x)

    return max(b.i-a.i for a,b in zip(stack, stack[1:]))

Пример:

>>> maxrange([2,1,3])
2

Ответ 2

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

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

В качестве примера, учитывая последовательность 4 1 0 3 2, мы получим это декартово дерево:

        4
         \
          3
         / \
        1   2
         \
          0

Обратите внимание, что перемещение по порядку действительно возвращает 4 1 0 3 2.

Теперь я утверждаю, что конечные точки диапазона, который мы ищем, должны быть родительской/дочерней парой в декартовом дереве (то есть либо первый node является родителем второго node Versa). Обратите внимание, что мы не ищем node и любого предка, но определенно родительскую/дочернюю пару. Чтобы доказать это, я докажу следующие две формулы:

Требование 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 не имеют между ними значений, которые противоречат друг другу или v или v. Предположим, что это так, и значение w больше, чем u или v. По определению декартова дерева, если w находится между u и v в исходной последовательности, то в случае (1) оно должно быть в поддерево A и в случае (2) оно должно быть в поддереве B. Но декартово дерево является макс-кучей, поэтому в случае (1) и u и v больше всех в A, а в случае (2) оба u и v больше, чем все в B, противоречие. Таким образом, диапазон значений между любой родительской/дочерней парой должен быть не больше, чем родительский или дочерний.

Доказательство по п. 2: По контрацептивным; мы показываем, что если существует подпоследовательность исходного массива, начинающаяся с u и заканчивающаяся на v, которая содержит элемент больше w, чем 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 метанодов.

В целях обозначения пусть "левый" node метанода будет node самым дальним влево в метаноме, а пусть "самый правый" node метанода будет node наиболее дальним до справа в метаноде.

В этом модифицированном декартовом дереве мы можем определить перемещение узлов по порядку как одно, которое посещает все узлы в метаноме в порядке слева направо, делая поход по каждому из узлов, которые он содержит. Затем мы устанавливаем, что модифицированное декартово дерево a строгое max-heap (каждый node должен быть строго больше любого из его дочерних элементов) и что перемещение по порядку дерева приводит к значениям в том же порядке в котором они появляются в исходной последовательности.

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

В этой модифицированной древовидной структуре диапазон значений без промежуточных значений, по крайней мере равных конечным точкам, соответствует:

• Родитель и самый правый node его левого дочернего элемента.
• Родительский и самый левый node своего правого ребенка.
• Два соседних узла в одном метаноде.

Доказательство первых двух утверждений является довольно простой модификацией доказательства для вышеуказанного случая. Разница в том, что вместо доказательства противоречия, говорящего о том, что это нарушит свойство max-heap, вместо этого вы утверждаете, что оно нарушает сильное свойство max-heap. Вы также сказали бы, что любые равные значения в середине диапазона должны были бы проявляться как узлы, которые предотвращали бы, чтобы конечные точки диапазона были левыми или правыми узлами в метаноде. Доказательство третьего утверждения (примерно) состоит в том, что любые узлы между двумя узлами должны быть строго меньше конечных точек, а если в середине было равное значение, то два узла не были бы смежными метанодами.

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

Уф! Это была потрясающая проблема. Я не знаю, является ли это идеальным решением, но, по крайней мере, доказывает, что это возможно в O (n) времени. Если кто-то придумает лучший ответ, я бы с удовольствием его увидел.

Ответ 3

Решение Rafals хорошо, но мы можем обойтись без стека и сохранить память. Вот краткая и эффективная реализация в O(n) время:

def highDist(seq):
    res, ltr, rtl = 0, 0, 0
    for i in range(len(seq)):
        if seq[i] >= seq[ltr]:
            res = max(res, i-ltr)
            ltr = i
        if seq[-i-1] >= seq[-rtl-1]:
            res = max(res, i-rtl)
            rtl = i
    return res

Запустите на примере ввода:

>>> print highDist([0, 10, 8, 9, 6, 7, 4, 10, 0])
6
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 9, 0])
4
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 7, 0])
2
>>> print highDist([])
0

Фокус в том, что если мы имеем две точки a и b s.t. все между ними меньше их, то максимальное расстояние, которое мы ищем, либо |b-a|, либо полностью вне диапазона. Следовательно, если мы разбиваем всю последовательность таким образом, один из них - это диапазон, который мы ищем.

Мы можем сделать раздел легко создающим поправку с каждого конца.

Ответ 4

Я не уверен, является ли следующее решение O (n), но это, безусловно, "почти O (n)", а также очень просто, всего несколько строк кода. Он основан на следующем наблюдении. Для любой пары индексов (i, j) нарисуйте дугу между ними, если интервал [i, j] обладает искомым свойством. Теперь заметим, что эти дуги можно рисовать так, чтобы они не пересекались. Тогда заметим, что наименьшие пары (i, я + 1) - все они имеют искомое свойство. Далее, большая пара всегда может быть построена путем сокращения двух меньших пар. Это приводит к следующей структуре: Начните с пар (i, я + 1) в связанном списке. Перейдите по связанному списку несколько раз и попробуйте заключить подряд ссылки. Этот алгоритм не зависит от порядка из-за свойства непересечения. Далее следует код Perl.

#!/usr/local/bin/perl -w
use strict;

my @values    = (0, 10, 8, 9, 6, 7, 4, 10, 0);           # original example.
@values       = map { int(100 * rand()) } 1..100;        # random testing.
my $nvalues   = @values;
my @intervals = (1..$nvalues-1);       # this encodes a linked list 0->1, 1->2, N-2->N-1

my $change = 0;
my ($maxi, $maxj) = (0, 1);            # initial solution
my $maxdelta = 1;

do {
   my ($jstart, $j) = (0, $intervals[0]);
   $change = 0;
   while ($j < $nvalues-1) {
      my $jnext = $intervals[$j];
      while ($jnext < $nvalues -1 && $values[$j] == $values[$jnext]) {
          $jnext = $intervals[$jnext];   # lookahead to skip intervals with identical boundaries
      }
      if ($values[$j] < $values[$jstart] && $values[$j] < $values[$jnext]) {
         $intervals[$jstart] = $jnext;                   # contraction step
         print STDERR "contraction to $j $jnext\n";
         $change = 1;
         $j = $jnext;
         if ($jnext - $jstart > $maxdelta) {
            $maxdelta = $jnext - $jstart;
            ($maxi, $maxj) = ($jstart, $jnext);
         }
      }
      else {
         ($jstart, $j) = ($j, $intervals[$j]);
      }
   }
   print STDERR "---\n";
}
while ($change);


my $jstart = 0;

while ($jstart < $nvalues -1) {
   my $jnext = $intervals[$jstart];
   local $, = " ";
   print STDERR @values[$jstart..$jnext], "\n";
   $jstart = $jnext;
}

print STDERR "solution $maxi $maxj\n";

Ответ 5

ETA: Нашли некоторые ошибки, извините. Я вернусь к этому после работы, это определенно интригующая проблема.

Написано в виде псевдокода; идея состоит в том, чтобы переместить окно из трех чисел по массиву и выполнить определенные сравнения, а затем обновить соответственно ваши левые и правые позиции.

// Define the initial window
w1=a[0], w2=a[1], w3=a[2]
// Will hold the length of the current maximum interval
delta_max = 0

// Holds the value of the current interval leftmost value
left=max(w1,w2,w3)
// Holds the position of the current interval leftmost value
lpos= *position of the chosen wi above*

// Holds the position of the current interval rightmost value
rpos = lpos + 1
// Holds the value of the current interval rightmost value
right = a[rpos]

i = 0
// Holds the position of the max interval leftmost value
lmax = 0
// Holds the position of the max interval rightmost value
rmax = 0

while (i<n-3) do
    i = i + 3
    w1=a[i], w2=a[i+1], w3=a[i+2]

    if (w1<left) and (w2<left) and (w3<left)
        right = w3
        rpos = i + 2
    else
        // Set the new left to the first value in the window that is bigger than the current left
        if (w1>left): left = w1, lpos = i
        else
            if (w2>left): left = w2, lpos = i+1
            else
                if (w3>left): left = w3, lpos = i+2


    delta = rpos-lpos
    if delta>dmax: dmax = delta, lmax = lpos, rmax = rpos
    lpos = rpos
    rpos = lpos + 1
    right = a[rpos]
end

Ответ 6

Линейное решение тихое. Мы будем использовать два указателя для окончаний сегмента, так что каждый элемент на нем не больше, чем первый элемент. Для фиксированного первого элемента (первый указатель) мы перемещаем второй указатель до тех пор, пока он не укажет на меньший или равный первому элементу. Если элемент во втором указателе велик или равен первому, мы можем обновить ответ с текущей длиной сегмента. И если он указывает на элемент, строго превышающий первый, мы должны перенести первый указатель на текущую позицию, потому что ни один сегмент mo не может начинать с него в последней позиции - текущий элемент будет больше конечной точки сегмента.

Этот алгоритм найдет максимальный по длине сегмент с левым элементом, меньшим или равным правому элементу, поэтому нам нужно повторить те же действия еще раз - идя справа налево.

Сложность - O (n), просто перемещая n-1 раз второй указатель и не более n-1 раза первой указатель.

Если моя идея неясна, задайте любые вопросы.

Ответ 7

Я написал решение проблемы. До сих пор выглядит корректно, работает со всеми входными данными, которые я пробовал. Это код на С++. Я хотел, чтобы решение было чистым и простым, что я мог получить, поэтому не использовал предложенное декартовое дерево или решение стека, а более простой подход: сначала разобрать синтаксический анализ и получить список допустимых интервалов (как предлагает Rafał Dowgird), и во второй раз определить интервал максимальной длины, который является решением.

void Solution(const int* vData, int vLen) { typedef std::pair Interval; typedef std::vector ListaIntervaleType; ListaIntervaleType ListaIntervale;

}