O（n）复杂度子段中最大值的最小值...

Question

前几天我采访了亚马逊。我无法回答其中一个问题让我满意。我在面试后试图得到答案，但到目前为止我还没有取得成功。这里是问题：

你有一个大小为n的整数数组。您将获得参数k，其中k < n。对于阵列中大小为k的连续元素的每个段，您需要计算最大值。您只需返回这些最大值的最小值。

例如给出1 2 3 1 1 2 1 1 1和k = 3答案是1。
段将是1 2 3,2 3 1,3 1 1,1 1 2,1 2 1,2 1 1,1 1 1。
每个段中的最大值是3，3，3，2，2，2，1。
这些值中的最小值是1因此答案是1。

我想出的最佳答案是复杂度O（n log k）。我所做的是创建一个第一个k元素的二叉搜索树，在树中获取最大值并将其保存在变量minOfMax中，然后使用数组中的其余元素一次循环一个元素，删除第一个元素在二叉搜索树中的前一个分段中，将新分段的最后一个元素插入树中，获取树中的最大元素，并将其与minOfMax进行比较，并将minOfMax中的最小值留在这两者中。

理想的答案需要是复杂度O（n）。 谢谢。

Answer 1

有一个非常聪明的方法可以做到这一点，这与this earlier question有关。这个想法是有可能建立一个queue data structure that supports enqueue, dequeue, and find-max in amortized O(1) time（有很多方法可以做到这一点;两个在原始问题中解释）。一旦你有了这个数据结构，首先将数组中的前k个元素添加到O（k）时间的队列中。由于队列支持O（1）find-max，因此可以在O（1）时间内找到这些k元素的最大值。然后，从队列中持续出队一个元素并入队（在O（1）时间）下一个数组元素。然后，您可以在O（1）中查询每个这些k元素子阵列的最大值。如果您追踪在阵列过程中看到的最小值，那么您可以使用O（n）时间，O（k） - 空间算法来查找k元素子阵列的最小最大值。

希望这会有所帮助！

Answer 2

@ templatetypedef的答案有用，但我认为我有一个更直接的方法。

开始通过计算最大为以下的（封闭的）间隔：

[k-1, k-1] 
[k-2, k-1] 
[k-3, k-1] 
... 
[0, k-1] 

注意，每个这些都可以在恒定的时间从前述一个来计算。

接下来，计算这些区间的最大值：

[k, k] 
[k, k+1] 
[k, k+2] 
... 
[k, 2k-1] 

现在，这些间隔：

[2k-1, 2k-1] 
[2k-2, 2k-1] 
[2k-3, 2k-1] 
... 
[k+1, 2k-1] 

接下来你从2K的间隔3K-1（ “转发间隔”），然后从3k-1降至2k + 1（“向后间隔”）。等到你到达数组的末尾。

把所有这些放到一张大桌子里。请注意，此表中的每个条目都需要一段时间来计算。观察表中最多有2 * n个间隔（因为每个元素在“向前间隔”的右侧出现一次，而在“向后间隔”的左侧出现一次）。现在

，如果[A，B]为宽度k的任何间隔，它必须包含0，K，2K正好一个，...

说它含有米* k个。

注意到区间[a，m * k-1]和[m * k，b]都在我们表格的某处。因此，我们可以简单地查找每个值的最大值，这两个值的最大值是区间[a，b]的最大值。

因此，对于宽度为k的任何间隔，我们可以使用我们的表在恒定时间内获得其最大值。我们可以在O（n）时间内生成表格。结果如下。

Answer 3

这里是templatetypedef的答案的实现（C＃）。

public static void printKMax(int[] arr, int n, int k) 
    { 
     Deque<int> qi = new Deque<int>(); 
     int i; 
     for (i=0;i< k; i++) // first window of the array 
     { 
      while ((qi.Count > 0) && (arr[i] >= arr[qi.PeekBack()])) 
      { 
       qi.PopBack(); 
      } 
      qi.PushBack(i); 
     } 

     for(i=k ;i< n; ++i) 
     { 
      Console.WriteLine(arr[qi.PeekFront()]); // the front item is the largest element in previous window. 
      while (qi.Count > 0 && qi.PeekFront() <= i - k) // this is where the comparison is happening! 
      { 
       qi.PopFront(); //now it's out of its window k 
      } 
      while(qi.Count>0 && arr[i]>=arr[qi.PeekBack()]) // repeat 
      { 
       qi.PopBack(); 
      } 
      qi.PushBack(i); 
     } 

     Console.WriteLine(arr[qi.PeekFront()]); 
    }