Блог

Главная - Вопросы по программированию - Найдите максимальный элемент во всех смежных подмассивах размера K, используя только очередь

Найдите максимальный элемент во всех смежных подмассивах размера K, используя только очередь

#java #algorithm #data-structures #queue

Вопрос:

Дан массив A и целое число K. Мы должны найти максимальный элемент во всех смежных подмножествах размера K, используя только очередь в JAVA.

Например:

 Input:
7 3
12 1 78 90 57 89 56

Output:
78 90 90 90 89

Как я могу решить эту проблему, используя только очередь на Java?

Комментарии:

1. дан массив и целое число, …, решите его, используя только очередь . Какая очередь? Что ты пробовал, где ты застрял? Пожалуйста, выберите один язык

2. Я могу решить эту проблему с помощью deque…Но я пытаюсь решить ее только с помощью очередей.

3. Вам понадобится функция, которая возвращает максимальный элемент в данной очереди. Затем вы создаете очередь и заполняете ее первыми K элементами вашего списка. После печати макса (с помощью первоначально упомянутой функции) вы отбрасываете первый элемент и добавляете новый. Повторяйте до тех пор, пока у вас не останется новых элементов.

Ответ №1:

Вы можете использовать Sliding Window технику, чтобы найти максимальный элемент во всех смежных подмассивах размера K .
Для этого нам нужно использовать a PriorityQueue , чтобы мы могли получить максимальный элемент определенного окна в постоянное время. Во-первых, добавьте все первые K элементы в очередь и верните первый максимум, затем выполните итерацию по остальным окнам/суб-массивам размера K , просто добавив новую головку и удалив хвост окна.
И на каждой итерации продолжайте возвращать peek (максимум) текущего окна.
Вот реализация:

 PriorityQueue<Integer> queue = 
new PriorityQueue<>(Collections.reverseOrder());
 
for (int i=0; i < K; i  )
    queue.add(arr[i]);
 
System.out.println(queue.peek()); // maximum element among first `K` elements
 
// Rest of the windows of size `K`
for (int i=K; i < N; i  )
{
    queue.remove(arr[i - K]); // first element from front
    queue.add(arr[i]);       // adding current element
    System.out.println(queue.peek()); // maximum element in current window
}

Комментарии:

1. Требуется ли для этого, чтобы целые числа были уникальными?

2. @Surt Нет, он также отлично будет работать с массивом с дубликатами.

3. PriorityQueue.remove(Object o) то есть занимает линейное (по размеру очереди) время O(K) . Это не лучше, чем сканировать окно в поисках элемента max.

4. @user58697 Да, это O(N*K) так, но, пожалуйста, прочитайте вопрос еще раз. ОП строго упомянул, что ему нужен подход, использующий только очередь . Насколько мне известно, это лучшая временная сложность, которую мы можем достичь, если используем очередь. O(N) возможно, если мы используем a deque , которое он уже знает. Если у вас есть более эффективный подход с использованием очереди, пожалуйста, поделитесь своей идеей.

Метки: ,