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

Для заданного массива целых чисел найдите максимальное расстояние между 2 точками (i и j), которые имеют более высокие значения, чем любой элемент между ними.

Пример:

values: 0 10  8  9  6  7  4 10  0
index : 0  1  2  3  4  5  6  7  8 

для значений выше решение равно i = 1, j = 7, но

  • , если значение индекса 7 равно 9 вместо 10, решение равно i = 3, j = 7
  • если значение индекса 7 равно 7 вместо 10, то решение равно i = 5, j = 7

Я не вижу решения в O (n) ... кто-нибудь?

Ответы [ 7 ]

21 голосов
/ 23 марта 2011

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

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

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

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

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

Stack-bars

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

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

Вот реализация на 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
21 голосов
/ 23 марта 2011

Я считаю, что следующий алгоритм выполняется за 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) путем прямой модификации стандартного алгоритма декартового дерева.

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

  1. Родитель и самый правый узел его левого потомка.
  2. Родитель и самый левый узел его правого потомка.
  3. Два соседних узла в одном и том же метаноде.

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

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

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

5 голосов
/ 29 марта 2011

Решение 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|, либо полностью выходит за пределы диапазона. Следовательно, если мы разделим всю последовательность таким образом, одним из них будет диапазон, который мы ищем.

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

0 голосов
/ 24 марта 2011

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

</p>

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

/************************************************************************/
/* Get valid Intervals                                                  */
/************************************************************************/
#define IS_LAST_ELEM (i == vLen-1)

int iIdxStart = -1;
for (int i=1; i < vLen; ++i)
{
    if (-1 == iIdxStart)
    {
        /* Searching for Interval START */

        if (!IS_LAST_ELEM)
        {
            if (vData[i+1] < vData[i])
            {
                iIdxStart = i;
            }
        }


    }
    else
    {
        /* Searching for Interval END */

        if (vData[iIdxStart] <= vData[i] || IS_LAST_ELEM)
        {
            /* stop condition: crt val > start value*/
            ListaIntervale.push_back(std::make_pair(iIdxStart,i));

            if (!IS_LAST_ELEM && vData[i+1] < vData[i])
            {
                iIdxStart = i;
            }
            else
            {
                iIdxStart = -1;
            }
        }



    }

}

/************************************************************************/
/* Concatenate intervals                                                */
/************************************************************************/

//int iMaxLenIntervalIdx = -1;
//int iMaxLenIntervalVal = 0;

ListaIntervaleType::iterator crt;
//for (crt=ListaIntervale.begin(); crt!=ListaIntervale.end(); crt++)
//{
//  ListaIntervaleType::iterator next = crt + 1;
//  if (next != ListaIntervale.end())
//  {
//      if (crt->second == next->first)
//      {
//          if (crt->second < crt->first && 
//              crt->second < next->second)
//          {
//              //concatenam
//              crt->second =  next->second;
//              crt = ListaIntervale.erase(next);
//          }
//      }
//  }
//}


/************************************************************************/
/* Get Max                                                              */
/************************************************************************/

ListaIntervaleType::iterator solution = ListaIntervale.begin();
int iMaxLen = 0;

for (crt=ListaIntervale.begin(); crt!=ListaIntervale.end(); crt++)
{
    int iCrtLen = crt->second - crt->first;
    if (iCrtLen > iMaxLen)
    {
        iMaxLen = iCrtLen;
        solution = crt;
    }

}   

/************************************************************************/
/* Print Solution                                                       */
/************************************************************************/

if (solution != ListaIntervale.end())
{
    wprintf(L"Solution idx=[%d-%d] val=[%d-%d]", solution->first, solution->second, vData[solution->first], vData[solution->second]);
}
else
{
    wprintf(L"Solution NOT FOUND");
}


return;

}

0 голосов
/ 23 марта 2011

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

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

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

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

0 голосов
/ 23 марта 2011

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's leftmost value
left=max(w1,w2,w3)
// Holds the position of the current interval's leftmost value
lpos= *position of the chosen wi above*

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

i = 0
// Holds the position of the max interval's leftmost value
lmax = 0
// Holds the position of the max interval's 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
0 голосов
/ 23 марта 2011

Я не уверен, является ли следующее решение O (n), но оно определенно «почти O (n)», а также очень просто, всего несколько строк кода. Он основан на следующем наблюдении. Для любой пары индексов (i, j) нарисуйте дугу между ними, если интервал [i, j] обладает искомым свойством. Теперь обратите внимание, что эти дуги можно нарисовать так, чтобы они не пересекались. Затем обратите внимание, что наименьшие пары (i, i + 1) - все они имеют искомое свойство. Далее, большую пару всегда можно построить путем сокращения двух меньших пар. Это приводит к следующей структуре: Начните с пар (i, 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";
...