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()]); 
    }