arrays - 数组中最后 k 个值的最大值，优于 O(n^2)

Question

我有一个包含 n 个元素的数组，对于每个元素，我都试图从最后 k 个值(包括当前值)中找到最大值？例如。给定 k,

int[] highestValues = new int[arr.Length];
for (int i = k - 1; i < arr.Length; i++)
{
    int highest = Int32.MinValue;
    for (int j = i - k; j <= i; j++)
    {
        highest = Math.Max(highest, arr[j]);
    }
    highestValues[i] = highest;
}

看起来这个算法的复杂度是 O(n^2)。我想知道是否有任何方法可以更快地做到这一点，例如不要在内循环中比较 k 个数字，而是重用上一个操作的结果。

Answer 1

这个问题有一个很好的解决方案，使用Dequeue数据结构(一种支持在第一个和最后一个位置添加和检查元素的结构)。

我们创建类 Entry 来存储元素的索引和该元素的值。观察时间复杂度大约是2*n = O(2*n) = O(n)(每个元素只添加一次到队列中，我们同样遍历队列中的每个元素一次:在队列的第一个或最后一个位置将其删除)。

伪代码:

class Entry {
    int value, index;
}

int [] highestValues;

Dequeue queue = new Dequeue();   

 for(int i = 0; i < arr.Length; i++){
        Entry en = new Entry(arr[i], i);
        while(queue.last().value <= en.value){//Remove all elements smaller than the current element.
            queue.removeLast();
        }
        queue.append(en);
        if(i >= k){
            highestValues[i] = queue.first().value;
            while(queue.first().index < i - k){//Remove all elements which has index out of the range
                 queue.removeFirst();
            }
        }
    }    
}