给出了一个数组a和一个整数k。在java中,我们必须仅使用队列在大小为k的所有连续子数组中找到max元素。例如:
Input:7 312 1 78 90 57 89 56Output:78 90 90 90 89
Input:
7 3
12 1 78 90 57 89 56
Output:
78 90 90 90 89
如何在java中仅使用队列解决此问题?
dgtucam11#
你可以用 Sliding Window 在所有大小的相邻子阵列中查找最大元素的技术 K .我们需要使用 PriorityQueue 为此,我们可以在恒定时间内检索特定窗口的max元素。首先,添加所有第一个 K 元素排队并返回第一个最大值,然后遍历其余大小的窗口/子数组 K 只需添加新的头部并移除窗口的尾部。在每次迭代中,不断返回 peek 当前窗口的(最大值)。下面是一个实现:
Sliding Window
K
PriorityQueue
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}
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条答案
按热度按时间dgtucam11#
你可以用
Sliding Window
在所有大小的相邻子阵列中查找最大元素的技术K
.我们需要使用
PriorityQueue
为此,我们可以在恒定时间内检索特定窗口的max元素。首先,添加所有第一个K
元素排队并返回第一个最大值,然后遍历其余大小的窗口/子数组K
只需添加新的头部并移除窗口的尾部。在每次迭代中,不断返回
peek
当前窗口的(最大值)。下面是一个实现: