我面临一个问题,我想编写一个算法,该算法可以返回更大数组中每个连续 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)) . 有谁知道是否有更快的方法来做到这一点,如果有,怎么做?