Минимальное значение максимальных значений в подсегментах… в O (n) сложности
Я брал интервью у Amazon несколько дней назад. Я не смог ответить удовлетворительно ни на один из вопросов, которые мне задали. Я пытался получить ответ после собеседования, но пока безуспешно. Вот вопрос:
У вас есть массив целых чисел размера n. Вам задан параметр k , где k 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). Спасибо.