阵列中最后一个k值的最高值，比O(n^2)更好

Question

i有一个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 数据结构（一种支持在第一和最后一个位置添加和检查元素的结构）。

我们创建类条目以存储该元素的元素和值的索引。观察到时间复杂度大约为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();
            }
        }
    }    
}

Answer 2

这是最大滑动窗口问题或滑动窗口中最大值的数组。

请参阅：

• http://flexaired.blogspot.gr/2013/05/array-oray-of-maximum-value-in-sliding-window.html
• http://tech-queries.blogspot.gr/2011/05/sliding-window-maximum.html

关键是允许从头开始和结束删除元素以保持最大值时的最大值。

的最大值。

来自来源的示例：

import java.util.ArrayDeque;
import java.util.Deque;

公共类滑动{

public static void maxSlidingWindow(int A[], int n, int w, int B[]) {
    Deque<Integer> Q = new ArrayDeque<Integer>();
    // Initialize deque Q for first window
    for (int i = 0; i < w; i++) {
        while (!Q.isEmpty() && A[i] >= A[Q.getLast()])
            Q.pollLast();
        Q.offerLast(i);
    }
    for (int i = w; i < n; i++) {
        B[i - w] = A[Q.getFirst()];
        // update Q for new window
        while (!Q.isEmpty() && A[i] >= A[Q.getLast()])
            Q.pollLast();
        // Pop older element outside window from Q
        while (!Q.isEmpty() && Q.getFirst() <= i - w)
            Q.pollFirst();
        // Insert current element in Q
        Q.offerLast(i);
    }
    B[n - w] = A[Q.getFirst()];
}
public static void main(String args[]) {
    int k = 20;
    int a[] = new int[100];
    for(int i=0; i<100; i++)
    a[i] = i;
    int b[] = new int[a.length - k + 1];
    maxSlidingWindow(a, a.length, k, b);
    System.out.println("Sliding Window Maximum is ");
    for (int i = 0; i < b.length; i++) {
        System.out.print(b[i] + ",");
    }
}

}

Answer 3

我有一个我相信有效的实现（在C＃中编码）：

public static int[] LastKHighestValues(int[] array, int k)
{
    int[] maxes = new int[array.Length];
    int indexOfCurrentMax = 0;
    int indexOfNextMax = 0;
    for (int i = 0; i < array.Length; i++)
    {
        if (indexOfNextMax <= indexOfCurrentMax ||
            array[i] > array[indexOfNextMax])
        {
            indexOfNextMax = i;
        }
        if (i - indexOfCurrentMax >= k)
        {
            indexOfCurrentMax = indexOfNextMax;
        }
        if (array[i] > array[indexOfCurrentMax])
        {
            indexOfCurrentMax = i;
        }

        maxes[i] = array[indexOfCurrentMax];
    }
    return maxes;
}

这个想法是，您要保留两个"指针"：一个到当前的最大值，另一个是在当前最大值到期后要去的下一件事。这可以在一个通过数组（o（n））中实现。

我有一些通过测试，但是我远不能确定我涵盖了每个角案：

Puzzle.LastKHighestValues(new[] {4, 3, 1}, 1).Should().Equal(new[] {4, 3, 1});
Puzzle.LastKHighestValues(new[] { 7, 7, 7 }, 3).Should().Equal(new[] { 7, 7, 7 });
Puzzle.LastKHighestValues(new[] { 7, 7, 7 }, 4).Should().Equal(new[] { 7, 7, 7 });
Puzzle.LastKHighestValues(new[] { 3, 2, 1 }, 2).Should().Equal(new[] { 3, 3, 2 });
Puzzle.LastKHighestValues(new[] { 7, 1, 4, 1, 1 }, 3).Should().Equal(new[] { 7, 7, 7, 4, 4 });
Puzzle.LastKHighestValues(new[] { 7, 8, 4, 9, 10 }, 2).Should().Equal(new[] { 7, 8, 8, 9, 10 });