Построить массив с из существующего массива

Question

Учитывая массив целых чисел A[1...n-1], где N длина массива A. Построить массив B таким образом, что B[i] = min(A[i], A[i+1], ..., A[i+K-1]), где K будет дан. Массив B будет иметь N-K + 1 элемент.

Мы можем решить проблему с использованием мини-кучи. Построить мини-кучу для k элементов - O (k). Для каждого следующего элемента удалите первый элемент и вставьте новый элемент и heapify.

Поэтому худшем случае, время - O ((п-к + 1) * к) + O (к) Space - O (к)

Можем ли мы сделать это лучше?

Answer 1

Мы можем сделать лучше, если в алгоритме из OP мы изменим дорогостоящую процедуру «heapify» на гораздо более дешевую «перевернутую» или «перевернутую». Это дает временную сложность O (n * log (k)).

Или, если мы перебираем входной массив и помещаем каждый элемент в мини-очередь размера 'k', мы можем сделать это в O (n) времени. Min-queue - очередь, которая может выполнять find-min в O (1) раз. Он может быть реализован как пара мини-стеков. См. this answer.