如何找到最大的一些固定的给定长度的每个子阵列的给定数组中 [英] How to find maximum of each subarray of some fixed given length in a given array

问题描述

我们给出n个元素和整数k的阵列。假设我们希望长度为k的一个窗口在阵列上滑动，报告包含在每个窗口中的最大值。例如，给定阵列

  15 10 9 16 20 14 13
 

由于长度为4的窗口，我们将输出

  [15 10 9 16] 20 14 13  - ＆GT;输出16
 15 10 9 16 20] 14 13 ---＆GT;输出20
 15 10 9 16 20 14 13  - ＆GT;输出20
 15 10 9 16 20 14 13] ---＆GT;输出20
 

因此​​，结果将是

  16 20 20 20
 

我快到通过跟踪在每个点窗口的最大元素的问题，但遇到了一个问题，当最大的元素被滑出窗外。在这一点上，我想不出一个快速的方法来找出现存最大的因素是什么。

有谁知道一个高效的算法来解决这个问题？

解决方案

<一个href=\"http://stackoverflow.com/questions/4802038/implement-a-queue-in-which-push-rear-pop-front-and-get-min-are-all-constan/4802327#4802327\">This旧的问题 讨论如何建立一个队列中的数据结构支持插入，出列，并找到分钟都在O（1）时间。注意，这是不会标准的优先级队列，而是在其中的任何一点，你可以找到它包含了O（1）时间的最小元素的值的队列。你可以很容易地修改这个结构，支持找到-Max在O（1），而不是找分钟，因为这是更贴近这个特殊的问题。

利用这种结构，可以按如下方式解决O（n）的这个问题时间：

1. 排队数组的第k个元素放入特殊的队列中。


2. 对于在阵列的其余部分的每个元素：
   
   
   
   1. 使用队列的查找-MAX操作报告当前子范围的最大元素。
   
   
   2. 出列从队列中的元素，而旧的范围的最后一个K-1的元素到位。
   
   
   3. 排队从序列的下一个元素，从而导致队列现在持有该序列的下一个K-元件子范围。
   
   

这总共需要O（n）的时间，因为你访问的每个数组元素一次，和入队各出队最多一次，调用find-MAX恰好n-k次。我认为这是pretty爽，因为复杂的独立的k个的，它不最初看起来像它一定是可能的。

希望这有助于！并感谢问一个很酷的问题！

We are given an array of n elements and an integer k. Suppose that we want to slide a window of length k across the array, reporting the largest value contained in each window. For example, given the array

15  10   9  16  20  14  13

Given a window of length 4, we would output

[15  10   9  16] 20  14  13   ---> Output 16
 15 [10   9  16  20] 14  13   ---> Output 20
 15  10 [ 9  16  20  14]  13  ---> Output 20
 15  10   9 [16  20  14  13]  ---> Output 20

So the result would be

16  20  20  20

I was approaching the problem by keeping track of the maximum element of the window at each point, but ran into a problem when the largest element gets slid out of the window. At that point, I couldn't think of a fast way to figure out what the largest remaining element is.

Does anyone know of an efficient algorithm for solving this problem?

解决方案

This older question discusses how to build a queue data structure supporting insert, dequeue, and find-min all in O(1) time. Note that this is not a standard priority queue, but instead is a queue in which at any point you can find the value of the smallest element it contains in O(1) time. You could easily modify this structure to support find-max in O(1) instead of find-min, since that's more relevant to this particular problem.

Using this structure, you can solve this problem in O(n) time as follows:

1. Enqueue the first k elements of the array into the special queue.
2. For each element in the rest of the array:
   1. Use the queue's find-max operation to report the largest element of the current subrange.
   2. Dequeue an element from the queue, leaving the last k-1 elements of the old range in place.
   3. Enqueue the next element from the sequence, causing the queue to now hold the next k-element subrange of the sequence.

This takes a total of O(n) time, since you visit each array element once, enqueuing and dequeuing each at most once, and calling find-max exactly n-k times. I think this is pretty cool, since the complexity is independent of k, which doesn't initially seem like it necessarily should be possible.

Hope this helps! And thanks for asking a cool question!

这篇关于如何找到最大的一些固定的给定长度的每个子阵列的给定数组中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！