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

Question

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

例如

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

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

Answer 1

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

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

我所说的方法非常简单,需要动态编程,并且时间复杂度为O(n).

Your Sample Input:
n=10 , W = 3

10 3
1 -2 5 6 0 9 8 -1 2 0

Answer = 5 6 6 9 9 9 8 2

概念:动态规划

算法:

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

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

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

   

3. 我们已经分为块,因为我们将以2种方式计算最大值A.)通过从左到右遍历B.)从右到左遍历.但是怎么样？

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

   

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

   

6. 现在我们必须找到每个子阵列或大小为'W'的窗口的最大值.所以,从index = 1开始到index = N-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,对于所有索引i,(i<=(n-k+1))值RL[i]和LR[i+w-1] 比较,并且这两者中的最大值是该子阵列的答案.

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

时间复杂度:O(n)

实施代码:

// Shashank Jain
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define LIM 100001 

using namespace std;

int arr[LIM]; // Input Array
int LR[LIM]; // maximum from Left to Right
int RL[LIM]; // maximum from Right to left
int max_val[LIM]; // number of subarrays(windows) will be n-k+1

int 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;
}  

运行代码链接

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

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

Let k* = The begin of block containing k
ans[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] )

否则(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] )

Answer 2

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;
}

由于每个元素入队并且在最近1次时出列,因此复杂度为
O(n + n)= O(2n)= O(n).
并且队列的大小不能超过限制k.所以空间复杂度= O(k).

Answer 3

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

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

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

• 使用堆栈建模队列.
  

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

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

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

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

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

1)

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

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

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

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

Answer 4

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

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