Построить массив B из массива A, чтобы каждый индекс был максимальным из k-го элемента в исходном массиве

Question

Дан массив A, длина n и натуральное число k, такое что 1 <= k <= n. Построить массив B размером n-k+1, который удовлетворяет следующему: каждый B[j] - это максимум между A[j],A[j+1],...A[j+k-1]

предположим, чтобы решить в линейное время например:

A = {3,1,5,12,13,4,2} size 7 and k = 3. desired answer would be -
B = {5,12,13,13,13}

Примечание; это не домашнее задание, а вопрос после экзамена, который мне трудно решить.

Попробовал использовать Double-Ended Queue, которая будет содержать максимум k элементов, но у меня возникла проблема с отслеживанием k-го максимума.

Answer 1

Я думаю, что это будет полезно: https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/. Третье решение - использовать деку для отслеживания максимального элемента в окнах из k элементов.Сложность будет O (n).

Answer 2

Обычно это проблема монотонной очереди.

Вот описание об этом. Прочитайте это, и это легко!

https://leetcode.com/problems/sliding-window-maximum/discuss/65885/this-is-a-typical-monotonic-queue-problem