给出了一个数组 A 和一个整数 K。我们必须仅使用JAVA 中的队列在所有大小为 K 的连续子数组中找到最大元素。
例如:
Input:
7 3
12 1 78 90 57 89 56
Output:
78 90 90 90 89
如何仅使用Java 中的队列来解决此问题?
您可以使用Sliding Window
技术在 size 的所有连续子数组中找到最大元素K
。
我们需要为此使用 aPriorityQueue
以便我们可以在恒定时间内检索特定窗口的最大元素。首先,将所有第一个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
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句