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

萨里克

给出了一个数组 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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

在未排序的对数组中查找 K 个唯一最大元素

Boolean 的解释 - 在未排序的数组中查找第 K 个最大元素

Java:使用2个数组查找数组的第K个最大元素

长度为k的所有子数组的元素的乘积和

查找数组中最大元素的所有索引

如何改进此代码以查找数组的 k 个最大元素?

支持第k个最大元素快速查找的队列数据结构

在数组中查找最大元素

长度为K的滑动窗口的最大元素之和

从二维数组中查找最大元素和最大元素列表的最有效方法?

使用“ ==”获取数组中的最大元素

数组中大小为K的连续组

给定一个大小为n的整数数组,找到第k个最大元素而不对整个数组进行排序

如何在O(n)中长度为n的未排序数组中找到第k个最大元素?

在n + 2k-3比较中找到大小为(2 ^ k +1)的数组中的第三大元素

使用递归查找数组中的最大元素

使用堆查找第K个最大元素的时间复杂度

在 Python 中使用 QuickSelect 查找第 K 个最大元素

使用快速选择算法查找第 k 个最大元素

子序列的最大长度,以使得每个连续元素的按位XOR为k

数组中的最大子集,使得最小和最大元素的间距小于K

向数组中插入绝对差后,找到数组中的第k个最大元素

查找列表中最大元素的所有索引

总和为 k 的子数组的最小大小

有效地查找数组中的最大元素

JavaScript:返回总和等于 K 的所有连续子数组

数组的K个最大元素,排序算法

如何找到已知大小的数组中的最大元素?

如何找到大小为k的所有子数组的第n个最小值/最大值(滑动窗口问题)