C++：在子数组的数组中查找最大整数

Question

我遇到一个问题，需要编写一个算法来返回一个大数组中每个连续的k元素子数组的最大元素，并将这些最大元素读入到它们自己的数组中，如下所示：

Given int array = {3, 7, 20, 6, 12, 2, 0, 99, 5, 16}, and int k = 4,
--> creates the array {20, 20, 20, 12, 99, 99, 99} 
[because there are 7 consecutive sub-arrays of size 4 within the given array:
{3, 7, 20, 6}, {7, 20, 6, 12}, {20, 6, 12, 2}, ... , {0, 99, 5, 16}
and the max element of these, respectively, is 20, 20, 20, ..., 99 which 
are read into the resulting array. 

现在我遇到的问题是：我知道如何使用O(n^2)复杂度实现它，但想要使其更快，即为O(n)，或者如果不可能，则为O(nlog(n))。有人知道是否有更快的方法来做到这一点吗？如果有，请告诉我具体如何操作。

- Rich

---

连续的子数组。抱歉，我忘记提到了。 - Rich

我认为，除非你有某种形式的启发式算法，否则在执行复杂度方面你无法使其更加高效。如果这些数据结构是树，则可以使用高级截断算法，例如alpha-beta剪枝。因此，不幸的是，我认为你只能使用递归使其更加优雅，并且你将被困在O(n^2)中。 - Aiden Strydom

你是不是指的是O(nk)复杂度而不是O(n^2)？朴素的方法似乎是扫描每个子数组中的k个元素并选择最大的一个。 - josliber

可能是Can min/max of moving window achieve in O(N)?的重复问题。 - MBo

Answer 1

首先，朴素算法的复杂度为O(k(n-k+1))（通常近似为O(k.n)），而不是O(n^2)。对于每个连续的子数组（共n-k+1个可能的子数组），您必须执行k次比较。

使用长度为k的附加数组maximums可以优化此算法，通过一些记忆化技巧。该数组将存储下一个最大值的索引。

在遍历数据集的每次迭代中，您检查maximums的第一个元素。删除任何“过期”的索引后，第一个元素就是当前迭代的答案。

当你在数据上滑动一个窗口（大小为k），你会将当前索引推入maximums，然后按照以下方式修剪它：索引maximums[i]处的值必须小于索引maximums[i-1]处的值。如果不是，则继续将索引向maximums的开头冒泡一次，直到这个条件成立。

实际上，最好将maximums数组视为环形缓冲区。修剪过程将把尾部缩回到头部，而弹出任何“过期”的最大值（当窗口滑过它们时）将使头部向前移动一步。

虽然有点笨重，但下面是一些可行的代码来说明：

#include <vector>
#include <iostream>

int main()
{
    const int window_size = 4;
    std::vector<int> vals = { 3, 7, 20, 6, 12, 2, 0, 99, 5, 16 };
    std::vector<int> maximums( window_size );
    int mhead = 0, mtail = 0;

    for( int i = 1; i < vals.size(); i ++ )
    {
        // Clean out expired maximum.
        if( maximums[mhead] + window_size <= i )
        {
            int next_mhead = (mhead + 1) % window_size;
            if( mtail == mhead ) mtail = next_mhead;
            mhead = next_mhead;
        }

        if( vals[i] >= vals[ maximums[mtail] ] )
        {
            // Replace and bubble up a new maximum value.
            maximums[mtail] = i;
            while( mhead != mtail && vals[ maximums[mtail] ] >= vals[ maximums[(mtail+window_size-1)%window_size] ] )
            {
                int prev_mtail = (mtail + window_size - 1) % window_size;
                maximums[prev_mtail] = maximums[mtail];
                mtail = prev_mtail;
            }
        }
        else
        {
            // Add a new non-maximum.
            mtail = (mtail + 1) % window_size;
            maximums[mtail] = i;
        }

        // Output current maximum.
        if( i >= window_size - 1 )
        {
            std::cout << vals[ maximums[mhead] ] << " ";
        }
    }

    std::cout << std::endl;
    return 0;
}

现在，时间复杂度...

最好情况是O(n)，当你的所有数据已排序（升序或降序）时发生。

最坏情况，我认为是O(2n)。只有在一次迭代中需要k额外操作的唯一方法是如果您已经进行了k步线性复杂度（以便环形缓冲区已满）。在这种情况下，环形缓冲区将在下一步为空。由于我们只能填充和清空环形缓冲区n/k次，那些偶尔的k操作会以k.n/k或n的形式出现。

您应该能够证明即使是常数部分清空环形缓冲区也会导致相同的复杂度。

最后，我们可以总结并称整个过程为O(n)，因为对于大的n，任何常数因子都变得微不足道。它实际上比我预期的要好。=）

- paddy

---

我可能应该提到，像许多算法一样，朴素方法可能更适用于小的 k 值，但随着 k 的增大，线性时间算法的优势开始显现。 - paddy