Постановка задачи :
Дан массив целых чисел размера N и число K, выведите максимальное значение каждого подмассива длины K в массиве.
Первая строка содержит два целых числа, разделенных одиночным пробелом, N и K.
Вторая строка содержит N целых чисел, разделенных одиночным пробелом, обозначающих элементы массива.
Пример ввода:
6 3 10 5 2 7 8 7
Пример вывода:
10 7 8 8
Подход :
Дек подход
- Создайте двустороннюю очередь. Обратите внимание, что двухсторонняя очередь будет хранить индексы элементов, а не сами элементы.
- Вставьте первые «K» элементов (первый подмассив) в очередь. При вставке текущего элемента проверьте, меньше ли элемент в конце очереди, чем текущий элемент. Если да, то удалите все эти элементы, а затем вставьте текущий элемент в конец двухсторонней очереди.
- После того, как вы это сделаете, в начале очереди будет индекс максимального элемента, присутствующего в первом подмассиве размера «K». Распечатайте элемент, присутствующий в переднем элементе (индекс элемента массива) двухсторонней очереди.
- Затем мы будем следовать той же идее и для следующих элементов, но будет один дополнительный шаг, который заключается в удалении всех элементов из передней части двухсторонней очереди, которые находятся вне диапазона рассматриваемого подмассива.
Временная сложность — O(N)
Пространственная сложность — O(K)
Код :
Спасибо за чтение
Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.
Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.
