仅使用队列查找大小为 K 的所有连续子数组中的最大元素

Question

给定一个数组A和一个整数K。我们必须使用 仅 JAVA.

中的队列 在所有大小为 K 的连续子数组中找到最大元素

例如：

Input:
7 3
12 1 78 90 57 89 56

Output:
78 90 90 90 89

如何使用 only queue in Java 来解决这个问题？

Answer 1

您可以使用 Sliding Window 技术在大小为 K 的所有连续子数组中找到最大元素。
我们需要为此使用 PriorityQueue 以便我们可以在恒定时间内检索特定 window 的最大元素。首先，将所有第一个 K 元素添加到队列中，然后将 return 第一个最大值添加到队列中，然后通过添加新的头部并移除大小 K 的其余 windows/sub-arrays 来迭代window.
的尾部并且在每次迭代中保持 returning 当前 window.
的 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
}

仅使用队列查找大小为 K 的所有连续子数组中的最大元素

Find the max element in all the contiguous subarray of size K using only queue

java

algorithm

queue

data-structures