Минимальное значение максимальных значений в подсегментах ... в сложности O (n) - PullRequest
Новая
       66

Минимальное значение максимальных значений в подсегментах ... в сложности O (n)

13 голосов
/ 14 декабря 2011

Я взял интервью у Amazon несколько дней назад. Я не мог ответить на один из вопросов, которые задавали мне, к их удовлетворению. Я пытался получить ответ после интервью, но пока не добился успеха. Вот вопрос:

У вас есть массив целых чисел размера n. Вам задан параметр k, где k < n. Для каждого сегмента последовательных элементов размером k в массиве необходимо рассчитать максимальное значение. Вам нужно только вернуть минимальное значение этих максимальных значений.

Например, если дано 1 2 3 1 1 2 1 1 1 и k = 3, ответ будет 1.
Сегменты будут 1 2 3, 2 3 1, 3 1 1, 1 1 2, 1 2 1, 2 1 1, 1 1 1.
Максимальные значения в каждом сегменте: 3, 3, 3, 2, 2, 2, 1.
Минимум этих значений 1, таким образом, ответ 1.

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

Идеальный ответ должен быть сложности O (n). Спасибо.

Ответы [ 3 ]

10 голосов
/ 14 декабря 2011

Существует очень умный способ сделать это, связанный с с этим более ранним вопросом . Идея состоит в том, что можно построить структуру данных queue, которая поддерживает enqueue, dequeue и find-max за время амортизации O (1) (есть много способов сделать это; два объяснены в оригинале вопрос). Получив эту структуру данных, начните с добавления первых k элементов из массива в очередь за O (k) раз. Поскольку очередь поддерживает O (1) find-max, вы можете найти максимум этих k элементов за O (1) раз. Затем непрерывно исключите элемент из очереди и поставьте в очередь (за O (1) раз) следующий элемент массива. Затем вы можете запросить в O (1), каково максимальное значение каждого из этих подмассивов k-элементов. Если вы отслеживаете минимальное из этих значений, которое вы видите в течение массива, то у вас есть O (n) -временной, O (k) -пространственный алгоритм для нахождения минимального максимума k-элементных подмассивов.

Надеюсь, это поможет!

9 голосов
/ 14 декабря 2011
Ответ

@ templatetypedef работает, но я думаю, что у меня есть более прямой подход.

Начните с вычисления максимального значения для следующих (закрытых) интервалов: 

[k-1, k-1]
[k-2, k-1]
[k-3, k-1]
...
[0, k-1]

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

Далее вычислите максимальное значение для этих интервалов: 

[k, k]
[k, k+1]
[k, k+2]
...
[k, 2k-1]

Теперь эти интервалы: 

[2k-1, 2k-1]
[2k-2, 2k-1]
[2k-3, 2k-1]
...
[k+1, 2k-1]

ДалееВы делаете интервалы от 2k до 3k-1 («прямые интервалы»), затем от 3k-1 до 2k + 1 («обратные интервалы»).И так до тех пор, пока вы не достигнете конца массива.

Поместите все это в большую таблицу.Обратите внимание, что каждая запись в этой таблице требует постоянного времени для вычисления.Обратите внимание, что в таблице не более 2 * n интервалов (поскольку каждый элемент появляется один раз с правой стороны от «интервала перемотки вперед» и один раз с левой стороны от «интервала перемотки назад»).

Теперь, если [a, b] - любой интервал ширины k, он должен содержать ровно один из 0, k, 2k, ...

Скажем, он содержит m * k.

Заметьте, чтоинтервалы [a, m * k-1] и [m * k, b] находятся где-то в нашей таблице.Таким образом, мы можем просто найти максимум для каждого, и максимум этих двух значений - это максимум интервала [a, b].

Так что для любого интервала ширины k мы можем использовать нашу таблицу дляполучить его максимум в постоянное время.Мы можем сгенерировать таблицу за O (n) раз.Результат следует.

0 голосов
/ 27 марта 2017

Я реализовал (и прокомментировал) ответ templatetypedef в C #.

n - длина массива, k - размер окна. 

    public static void printKMax(int[] arr, int n, int k)
    {
        Deque<int> qi = new Deque<int>(); 
        int i;

        for (i=0 ; i < k ; i++) // The first window of the array
        {
            while ((qi.Count > 0) && (arr[i] >= arr[qi.PeekBack()]))
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }

        for(i=k ; i < n ; ++i)
        {
            Console.WriteLine(arr[qi.PeekFront()]); // the first item is the largest element in previous window. The second item is its index.

            while (qi.Count > 0 && qi.PeekFront() <= i - k) 
            {
                qi.PopFront(); //When it's out of its window k 
            }
            while (qi.Count>0 && arr[i] >= arr[qi.PeekBack()]) 
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }
        Console.WriteLine(arr[qi.PeekFront()]);
    }
...