algorithm - 查找数组中每个大小为 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 block 。

   这里分成大小为'W'=3的 block 。对于您的示例输入:

   

3. 我们分成 block 是因为我们将以两种方式计算最大值 A.) 从左到右遍历 B.) 从右到左遍历。但是如何？？

4. 首先，从左到右遍历。对于每个元素 ai在 block 中，我们将找到该元素之前的最大值 ai从 block 的开始到该 block 的结束。所以在这里，

   

5. 其次，从右到左遍历。对于每个元素 'ai'在 block 中，我们将找到该元素之前的最大值 'ai'从 block 的 END 开始到该 block 的 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, 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.

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

时间复杂度:O(n)

实现代码:

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

Running Code Link

---

我会尝试证明:(@johnchen902)

如果k % w != 1 (k 不是 block 的开始)

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 是 block 的开始)

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] )