как найти n-й минимум / максимум всех подмассивов размера k (проблема со скользящим окном)

Question

Существует так много ссылок, чтобы найти минимум / максимум всех подмассивов размера k, но как найти n-й максимум / минимум наилучшим образом. Если нам нужно найти только минимальное / максимальное количество подмассивов, то мы можем использовать решение deque с линейной сложностью по времени. Но в течение n-й мин / макс я не могу найти решение.

Примечание: n <= k </p>

Пример: обр = {7,1,4,20,11,17,15} n = 2, k = 4

вывод: 4,4,11,15

Answer 1

Я считаю, что необходимая вам структура данных - это немного измененное двоичное дерево поиска (BST), где каждый узел также хранит размер своего поддерева.

Добавление, удаление элементов или поиск n-го элемента в BST все становится log(K)*.Таким образом, при перемещении окна по вашему массиву у вас есть 3 log(K) операций, при условии, что общее количество элементов в данном массиве составляет N, поэтому общая сложность времени составляет N*log(K).

• . Вам необходимо сбалансированноеBST (например, Red Black Tree), чтобы поддерживать сложность этого времени.Если вы работаете с любыми онлайн-судьями, такими как Codeforce или Hackerrank, помните, что они чаще всего предоставляют данные, которые будут генерировать вырожденные BST.