查找数组中每个大小为k的窗口的最大值

Given an array of size n and k, how do you find the maximum for every contiguous subarray of size k?

给定一个大小为n和k的数组,如何找到每个大小为k的连续子数组的最大值?

For example

arr = 1 5 2 6 3 1 24 7k = 3ans = 5 6 6 6 24 24

I was thinking of having an array of size k and each step evict the last element out and add the new element and find maximum among that. It leads to a running time of O(nk). Is there a better way to do this?

我正在考虑使用一个大小为k的数组,每一步都将最后一个元素逐出,并添加新元素并在其中找到最大元素。它导致O(nk)的运行时间。有一个更好的方法吗?

17 个解决方案

#1

You need a fast data structure that can add, remove and query for the max element in less than O(n) time (you can just use an array if O(n) or O(nlogn) is acceptable). You can use a heap, a balanced binary search tree, a skip list, or any other sorted data structure that performs these operations in O(log(n)).

您需要一个快速的数据结构,可以在少于O(n)的时间内添加,删除和查询max元素(如果可以接受O(n)或O(nlogn),则可以使用数组)。您可以使用堆,平衡二叉搜索树,跳过列表或在O(log(n))中执行这些操作的任何其他已排序数据结构。

The good news is that most popular languages have a sorted data structure implemented that supports these operations for you. C++ has std::set and std::multiset (you probably need the latter) and Java has TreeSet.

好消息是,大多数流行语言都有一个已实现的排序数据结构,可以为您支持这些操作。 C ++有std :: set和std :: multiset(你可能需要后者)而Java有TreeSet。

#2

You have heard about doing it in O(n) using dequeue.

您已经听说过使用dequeue在O(n)中执行此操作。

Well that is a well known algorithm for this question to do in O(n).

那么这是O(n)中这个问题的一个众所周知的算法。

The method i am telling is quite simple and requires Dynamic Programming and has time complexity O(n).

我所说的方法很简单,需要动态编程,时间复杂度为O(n)。

Your Sample Input:n=10 , W = 310 31 -2 5 6 0 9 8 -1 2 0Answer = 5 6 6 9 9 9 8 2

Concept: Dynamic Programming

概念:动态规划

Algorithm:

1. N is number of elements in an array and W is window size. So, Window number = N-W+1

N是数组中元素的数量,W是窗口大小。因此,窗口编号= N-W + 1

2. Now divide array into blocks of W starting from index 1.

   现在从索引1开始将数组分成W块。

   Here divide into blocks of size 'W'=3.For your sample input:

   这里划分为大小为'W'= 3的块。对于您的样本输入:

   

3. We have divided into blocks because we will calculate maximum in 2 ways A.) by traversing from left to right B.) by traversing from right to left.but how ??

   我们已经划分为块,因为我们将以2种方式计算最大值A.)通过从左到右遍历B.)通过从右到左遍历。但是如何?

4. Firstly, Traversing from Left to Right. For each element ai in block we will find maximum till that element ai starting from START of Block to END of that block.So here,

   首先,从左到右穿越。对于块中的每个元素ai,我们将找到最大值,直到元素ai从块的START开始到该块的END。所以这里,

   

5. Secondly, Traversing from Right to Left. For each element 'ai' in block we will find maximum till that element 'ai' starting from END of Block to START of that block.So Here,

   其次,从右到左穿越。对于块中的每个元素'ai',我们将找到最大值,直到元素'ai'从块的END开始到该块的START。所以这里,

   

6. Now we have to find maximum for each subarray or window of size 'W'.So, starting from index = 1 to index = N-W+1 .

   现在我们必须找到大小为'W'的每个子阵列或窗口的最大值。因此,从index = 1开始到index = N-W + 1。

   max_val[index] = max(RL[index], LR[index+w-1]);

   max_val [index] = max(RL [index],LR [index + w-1]);

   

    for index=1: max_val[1] = max(RL[1],LR[3]) = max(5,5)= 5

Simliarly, for all index i, (i<=(n-k+1)), value at RL[i] and LR[i+w-1] are compared and maximum among those two is answer for that subarray.

同时,对于所有索引i,(i <=(n-k + 1)),比较RL [i]和LR [i + w-1]的值,并且这两个中的最大值是该子阵列的答案。

So Final Answer : 5 6 6 9 9 9 8 2

所以最终答案:5 6 6 9 9 9 8 2

Time Complexity: O(n)

时间复杂度:O(n)

Implementation code:

// Shashank Jain#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LIM 100001 using namespace std;int arr[LIM]; // Input Arrayint LR[LIM]; // maximum from Left to Rightint RL[LIM]; // maximum from Right to leftint max_val[LIM]; // number of subarrays(windows) will be n-k+1int main(){    int n, w, i, k; // 'n' is number of elements in array                    // 'w' is Window's Size     cin >> n >> w;    k = n - w + 1; // 'K' is number of Windows    for(i = 1; i <= n; i++)        cin >> arr[i];    for(i = 1; i <= n; i++){ // for maximum Left to Right        if(i % w == 1) // that means START of a block            LR[i] = arr[i];        else            LR[i] = max(LR[i - 1], arr[i]);            }    for(i = n; i >= 1; i--){ // for maximum Right to Left        if(i == n) // Maybe the last block is not of size 'W'.             RL[i] = arr[i];         else if(i % w == 0) // that means END of a block            RL[i] = arr[i];        else            RL[i] = max(RL[i+1], arr[i]);    }    for(i = 1; i <= k; i++)    // maximum        max_val[i] = max(RL[i], LR[i + w - 1]);    for(i = 1; i <= k ; i++)        cout << max_val[i] << " ";    cout << endl;    return 0;}  

Running Code Link

运行代码链接

---

I'll try to proof: (by @johnchen902)

我会试着证明:(来自@ johnchen902)

If k % w != 1 (k is not the begin of a block)

如果k%w!= 1(k不是块的开头)

Let k* = The begin of block containing kans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])       = max( max( arr[k],  arr[k + 1],  arr[k + 2],  ..., arr[k*]),               max( arr[k*], arr[k* + 1], arr[k* + 2], ..., arr[k + w - 1]) )       = max( RL[k], LR[k+w-1] )

Otherwise (k is the begin of a block)

否则(k是块的开头)

ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])       = RL[k] = LR[k+w-1]       = max( RL[k], LR[k+w-1] )

#3

Dynamic programming approach is very neatly explained by Shashank Jain. I would like to explain how to do the same using dequeue.The key is to maintain the max element at the top of the queue(for a window ) and discarding the useless elements and we also need to discard the elements that are out of index of current window.
useless elements = If Current element is greater than the last element of queue than the last element of queue is useless .
Note : We are storing the index in queue not the element itself. It will be more clear from the code itself.
1. If Current element is greater than the last element of queue than the last element of queue is useless . We need to delete that last element.(and keep deleting until the last element of queue is smaller than current element).
2. If if current_index - k >= q.front() that means we are going out of window so we need to delete the element from front of queue.

Shashank Jain非常巧妙地解释了动态编程方法。我想解释如何使用dequeue做同样的事情。关键是将max元素保持在队列的顶部(对于一个窗口)并丢弃无用的元素,我们还需要丢弃超出索引的元素当前窗口。无用的元素=如果当前元素大于队列的最后一个元素,那么队列的最后一个元素是无用的。注意:我们将索引存储在队列中而不是元素本身。代码本身会更清楚。 1.如果Current元素大于队列的最后一个元素,则队列的最后一个元素是无用的。我们需要删除最后一个元素。(并继续删除,直到队列的最后一个元素小于当前元素)。 2.如果current_index - k> = q.front()表示我们要离开窗口,那么我们需要从队列前面删除该元素。

vector<int> max_sub_deque(vector<int> &A,int k){    deque<int> q;    for(int i=0;i<k;i++)    {        while(!q.empty() && A[i] >= A[q.back()])            q.pop_back();        q.push_back(i);    }    vector<int> res;    for(int i=k;i<A.size();i++)    {        res.push_back(A[q.front()]);        while(!q.empty() && A[i] >= A[q.back()] )            q.pop_back();        while(!q.empty() && q.front() <= i-k)            q.pop_front();        q.push_back(i);     }    res.push_back(A[q.front()]);    return res;}

Since each element is enqueued and dequeued atmost 1 time to time complexity is
O(n+n) = O(2n) = O(n).
And the size of queue can not exceed the limit k . so space complexity = O(k).

由于每个元素入队并且最多出现1次时间复杂度是O(n + n)= O(2n)= O(n)。并且队列的大小不能超过限制k。所以空间复杂度= O(k)。

#4

An O(n) time solution is possible by combining the two classic interview questions:

通过结合两个经典的面试问题,可以实现O(n)时间解决方案:

• Make a stack data-structure (called MaxStack) which supports push, pop and max in O(1) time.
  

  制作一个堆栈数据结构(称为MaxStack),在O(1)时间内支持push,pop和max。

  This can be done using two stacks, the second one contains the minimum seen so far.

  这可以使用两个堆栈来完成,第二个堆栈包含到目前为止看到的最小值。

• Model a queue with a stack.
  

  使用堆栈建模队列。

  This can done using two stacks. Enqueues go into one stack, and dequeues come from the other.

  这可以使用两个堆栈来完成。入队进入一个堆叠,出列队列来自另一个。

For this problem, we basically need a queue, which supports enqueue, dequeue and max in O(1) (amortized) time.

对于这个问题,我们基本上需要一个队列,它在O(1)(摊销)时间内支持入队,出队和最大化。

We combine the above two, by modelling a queue with two MaxStacks.

我们通过使用两个MaxStack对队列建模来组合上述两个。

To solve the question, we queue k elements, query the max, dequeue, enqueue k+1 th element, query the max etc. This will give you the max for every k sized sub-array.

为了解决这个问题,我们排队k个元素,查询max,dequeue,将k + 1个元素排队,查询max等。这将为每个k大小的子数组提供最大值。

I believe there are other solutions too.

我相信还有其他解决方案。

1)

I believe the queue idea can be simplified. We maintain a queue and a max for every k. We enqueue a new element, and dequeu all elements which are not greater than the new element.

我相信队列的想法可以简化。我们为每个k维护一个队列和一个最大值。我们将一个新元素排入队列,并将所有不大于新元素的元素取消。

2) Maintain two new arrays which maintain the running max for each block of k, one array for one direction (left to right/right to left).

2)维护两个新阵列,其保持每个k块的运行最大值,一个阵列用于一个方向(从左到右/从右到左)。

3) Use a hammer: Preprocess in O(n) time for range maximum queries.

3)使用锤子:在O(n)时间内预处理以进行范围最大查询。

The 1) solution above might be the most optimal.

上述1)解决方案可能是最优化的。

#5

Using a heap (or tree), you should be able to do it in O(n * log(k)). I'm not sure if this would be indeed better.

使用堆(或树),您应该能够在O(n * log(k))中执行此操作。我不确定这是否会更好。

#6

Here is the java implementation

这是java实现

public static Integer[] maxsInEveryWindows(int[] arr, int k) {    Deque<Integer> deque = new ArrayDeque<Integer>();    /* Process first k (or first window) elements of array */    for (int i = 0; i < k; i++) {        // For very element, the previous smaller elements are useless so        // remove them from deque        while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {            deque.removeLast(); // Remove from rear        }        // Add new element at rear of queue        deque.addLast(i);    }    List<Integer> result = new ArrayList<Integer>();    // Process rest of the elements, i.e., from arr[k] to arr[n-1]    for (int i = k; i < arr.length; i++) {        // The element at the front of the queue is the largest element of        // previous window, so add to result.        result.add(arr[deque.getFirst()]);        // Remove all elements smaller than the currently        // being added element (remove useless elements)        while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {            deque.removeLast();        }        // Remove the elements which are out of this window        while (!deque.isEmpty() && deque.getFirst() <= i - k) {            deque.removeFirst();        }        // Add current element at the rear of deque        deque.addLast(i);    }    // Print the maximum element of last window    result.add(arr[deque.getFirst()]);    return result.toArray(new Integer[0]);}

Here is the corresponding test case

这是相应的测试用例

@Testpublic void maxsInWindowsOfSizeKTest() {    Integer[] result = ArrayUtils.maxsInEveryWindows(new int[]{1, 2, 3, 1, 4, 5, 2, 3, 6}, 3);    assertThat(result, equalTo(new Integer[]{3, 3, 4, 5, 5, 5, 6}));    result = ArrayUtils.maxsInEveryWindows(new int[]{8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, 4);    assertThat(result, equalTo(new Integer[]{10, 10, 10, 15, 15, 90, 90}));}

#7

Using Fibonacci heap, you can do it in O(n + (n-k) log k), which is equal to O(n log k) for small k, for k close to n this becomes O(n).

使用Fibonacci堆,你可以在O(n +(n-k)log k)中进行,对于小k,它等于O(n log k),对于接近n的k,它变为O(n)。

The algorithm: in fact, you need:

算法:实际上,你需要:

• n inserts to the heap

n插入堆

• n-k deletions
• n-k findmax's

How much these operations cost in Fibonacci heaps? Insert and findmax is O(1) amortized, deletion is O(log n) amortized. So, we have

Fibonacci堆中这些操作的成本是多少? Insert和findmax是O(1)摊销,删除是O(log n)摊销。所以,我们有

O(n + (n-k) log k + (n-k)) = O(n + (n-k) log k)

#8

Sorry, this should have been a comment but I am not allowed to comment for now.@leo and @Clay GoddardYou can save yourselves from re-computing the maximum by storing both maximum and 2nd maximum of the window in the beginning(2nd maximum will be the maximum only if there are two maximums in the initial window). If the maximum slides out of the window you still have the next best candidate to compare with the new entry. So you get O(n) , otherwise if you allowed the whole re-computation again the worst case order would be O(nk), k is the window size.

对不起,这应该是评论,但我暂时不能发表评论。@ leo和@Clay Goddard你可以通过在开头存储窗口的最大和第二个最大值来避免重新计算最大值(第二个最大值将会只有在初始窗口中有两个最大值时才是最大值)。如果最大滑出窗口,您仍然有下一个与新条目进行比较的最佳候选者。所以你得到O(n),否则如果你再次允许整个重新计算,最坏的情况顺序将是O(nk),k是窗口大小。

#9

class MaxFinder{    // finds the max and its index    static int[] findMaxByIteration(int arr[], int start, int end)    {        int max, max_ndx;         max = arr[start];        max_ndx = start;        for (int i=start; i<end; i++)        {            if (arr[i] > max)            {                max = arr[i];                max_ndx = i;            }            }        int result[] = {max, max_ndx};        return result;    }    // optimized to skip iteration, when previous windows max element     // is present in current window    static void optimizedPrintKMax(int arr[], int n, int k)    {        int i, j, max, max_ndx;        // for first window - find by iteration.            int result[] = findMaxByIteration(arr, 0, k);        System.out.printf("%d ", result[0]);        max = result[0];        max_ndx = result[1];            for (j=1; j <= (n-k); j++)         {            // if previous max has fallen out of current window, iterate and find            if (max_ndx < j)              {                result = findMaxByIteration(arr, j, j+k);                max = result[0];                max_ndx = result[1];               }             // optimized path, just compare max with new_elem that has come into the window             else             {                int new_elem_ndx = j + (k-1);                if (arr[new_elem_ndx] > max)                {                    max = arr[new_elem_ndx];                    max_ndx = new_elem_ndx;                }                  }            System.out.printf("%d ", max);         }       }         public static void main(String[] args)    {        int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};        //int arr[] = {1,5,2,6,3,1,24,7};        int n = arr.length;        int k = 3;        optimizedPrintKMax(arr, n, k);    }}    

#10

package com;public class SlidingWindow {    public static void main(String[] args) {        int[] array = { 1, 5, 2, 6, 3, 1, 24, 7 };        int slide = 3;//say        List<Integer> result = new ArrayList<Integer>();        for (int i = 0; i < array.length - (slide-1); i++) {            result.add(getMax(array, i, slide));        }        System.out.println("MaxList->>>>" + result.toString());    }    private static Integer getMax(int[] array, int i, int slide) {        List<Integer> intermediate = new ArrayList<Integer>();        System.out.println("Initial::" + intermediate.size());        while (intermediate.size() < slide) {            intermediate.add(array[i]);            i++;        }        Collections.sort(intermediate);        return intermediate.get(slide - 1);    }}

#11

Here is the solution in O(n) time complexity with auxiliary deque

这是具有辅助双端的O(n)时间复杂度的解决方案

public class TestSlidingWindow {    public static void main(String[] args) {        int[] arr = { 1, 5, 7, 2, 1, 3, 4 };        int k = 3;        printMaxInSlidingWindow(arr, k);    }    public static void printMaxInSlidingWindow(int[] arr, int k) {        Deque<Integer> queue = new ArrayDeque<Integer>();        Deque<Integer> auxQueue = new ArrayDeque<Integer>();        int[] resultArr = new int[(arr.length - k) + 1];        int maxElement = 0;        int j = 0;        for (int i = 0; i < arr.length; i++) {            queue.add(arr[i]);            if (arr[i] > maxElement) {                maxElement = arr[i];            }    /** we need to maintain the auxiliary deque to maintain max element  in case max element is removed.         We add the element to deque straight away if subsequent element is less than the last element        (as there is a probability if last element is removed this element can be max element) otherwise         remove all lesser element then insert current element **/            if (auxQueue.size() > 0) {                if (arr[i] <  auxQueue.peek()) {                    auxQueue.push(arr[i]);                } else {                    while (auxQueue.size() > 0 && (arr[i] >  auxQueue.peek())) {                        auxQueue.pollLast();                    }                    auxQueue.push(arr[i]);                }            }else {                auxQueue.push(arr[i]);            }            if (queue.size() > 3) {                int removedEl = queue.removeFirst();                if (maxElement == removedEl) {                    maxElement = auxQueue.pollFirst();                }            }            if (queue.size() == 3) {                resultArr[j++] = maxElement;            }        }        for (int i = 0; i < resultArr.length; i++) {            System.out.println(resultArr[i]);        }    }}

#12

    static void countDistinct(int arr[], int n, int k)     {         System.out.print("\nMaximum integer in the window : ");        // Traverse through every window        for (int i = 0; i <= n - k; i++) {               System.out.print(findMaximuminAllWindow(Arrays.copyOfRange(arr, i, arr.length), k)+ " ");           }    }     private static int findMaximuminAllWindow(int[] win, int k) {        // TODO Auto-generated method stub        int max= Integer.MIN_VALUE;        for(int i=0; i<k;i++) {            if(win[i]>max)                max=win[i];        }        return max;    }

#13

Just notice that you only have to find in the new window if:* The new element in the window is smaller than the previous one (if it's bigger, it's for sure this one).OR* The element that just popped out of the window was the current bigger.

请注意,您只需要在新窗口中找到以下内容:*窗口中的新元素小于前一个元素(如果它更大,那肯定是这个)。或者*刚刚弹出窗口的元素当前更大。

In this case, re-scan the window.

在这种情况下,请重新扫描窗口。

#14

A complete working solution in Amortised Constant O(1) Complexity. https://github.com/varoonverma/code-challenge.git

一个完全工作的解决方案,摊销常数O(1)复杂性。 https://github.com/varoonverma/code-challenge.git

#15

I have created a simple solution, that need no fancy things. The idea is to keep track of the max from the previous window and update it only when it is needed.

我已经创建了一个简单的解决方案,不需要花哨的东西。我们的想法是跟踪前一个窗口的最大值,并仅在需要时更新它。

void printKMax(int arr[], int n, int k){    int max = arr[0];    // find max of initial k elements.    for (int i = 1; i < k; i++) {        if (arr[i] > max)            max = arr[i];    }    printf("%d ", max);    for (int i = k; i < n; i++) {        if (arr[i] > max) // Compare it with just next element.            max = arr[i];        printf("%d ", max);    }}

I didn't understand, is their any problem with this code, why it didn't anyone's mind. Time complexity => O(n)

我不明白,这是他们对这段代码的任何问题,为什么它没有人的想法。时间复杂度=> O(n)

#16

for how big k? for reasonable-sized k. you can create k k-sized buffers and just iterate over the array keeping track of max element pointers in the buffers - needs no data structures and is O(n) k^2 pre-allocation.

多大的k?对于合理大小的k。你可以创建k k大小的缓冲区,只是遍历数组,跟踪缓冲区中的max元素指针 - 不需要数据结构,并且是O(n)k ^ 2预分配。

#17

Compare the first k elements and find the max, this is your first number

比较前k个元素并找到最大值,这是你的第一个数字

then compare the next element to the previous max. If the next element is bigger, that is your max of the next subarray, if its equal or smaller, the max for that sub array is the same

然后将下一个元素与之前的最大值进行比较。如果下一个元素更大,那就是下一个子数组的最大值,如果它等于或小于,则该子数组的最大值相同

then move on to the next number

然后转到下一个号码

max(1 5 2) = 5max(5 6) = 6max(6 6) = 6... and so onmax(3 24) = 24max(24 7) = 24

It's only slightly better than your answer

它只比你的答案略胜一筹