在線進行了練習技術面試,,,我錯過了什麼？

Question

我正準備很快面試工作，並進行了一次實踐技術測試。我在問題上做得很好，除了這一個...

問題的前提是：給定一個數組，找到大小爲「n」的數組的順序子集的最大差異。示例

input = [6,8,4,5,3,1,7], n=3 
[6,8,4] = the biggest diff = 4 (8-4) 
[8,4,5] = the biggest diff = 4 (8-4) 
[4,5,3] = 2 
[5,3,1] = 4 
[3,1,7] = 6 
Final return from function:6 

輸入限制類似於：數組的長度將小於100k，n將小於數組的長度。 該功能必須在2秒內完成。

我最初在python中寫過這個，但只接收了3/6正確的測試用例，3個因時間限制而失敗，所以我重寫了C，希望獲得更好的性能。

int i,j; 
int maxdiff = 0; 
int localmax,localmin,localdiff; 
for (i=0;i<v_length-d+1;i++){ 
    localmax = v[i]; 
    localmin = v[i]; 
    localdiff = 0; 
    for(j=0;j<d;j++){ 
     if(v[j+i] > localmax){ 
      localmax = v[j+i]; 
     } 
     if(v[j+i] < localmin){ 
      localmin = v[j+i]; 
     } 
    } 
    localdiff = localmax-localmin; 
    if(localdiff > maxdiff){ 
     maxdiff = localdiff; 
    } 
} 
return maxdiff; 

我試着運行這個，但結果相同。 3/6正確，3/6由於運行時間而失敗。

我在這裏錯過了什麼嗎？我意識到我循環遍歷數組ArraySize中的每個值n次，我可以以某種方式在我的腦海中形象化地看到它可能只循環一次數組，但似乎無法弄清楚如何。 有什麼建議嗎？ 謝謝！

Answer 1

你可以在O（nlogn）中使用一個最小堆和一個最大堆來完成這個子集。 遍歷陣列時從堆中刪除第一個元素並添加新元素

Answer 2

解決涉及長輸入序列的連續子序列的問題的最簡單方法是使用（單端）隊列，至少在概念上。 （在輸入是矢量而不是流的情況下，實際上不需要存儲隊列，但是如果隊列明確，則算法通常更清晰。）

在這種情況下，解決方案需要找出隊列中最大和最小之間的最大差異。如果我們想要一個O(1)解決方案，我們需要一個隊列，其操作push_back,pop_front,min和max都是O(1)。

首先要注意的事情是，如果我們與該屬性（其中pop_front替換pop_back）尋找堆棧，解決辦法很簡單：每當我們推一個新的價值，我們計算出新分鐘最大值，並將它們與新值一起推送。當我們彈出一個值時，我們也彈出關聯的最小值和最大值，並且堆棧頂部剩餘的最小值和最大值再次正確。

我們如何將其轉換爲隊列？答案是我們需要使用堆棧來實現隊列。或者更準確地說，使用兩個堆棧。這就是所謂的「銀行家隊列」，它使用兩個（功能）堆棧提供了一個已攤銷的O(1)（功能）隊列。

這是一個簡單的技巧：其中一個堆棧 - 前堆棧 - 用於推送，另一個堆棧 - 後堆棧 - 用於彈出。隊列的前端保留在前端堆棧中，隊列的後端在後端堆棧上保持相反的順序，以便後端堆棧的頂端是隊列中的第一個元素。這工作正常，直到後退堆棧是空的，我們需要彈出第一個元素。此時，我們只需從前面的堆棧中逐個彈出一個元素，並將每個元素推到後面的堆棧上。一旦我們完成了，前端堆棧是空的，後端堆棧的頂端是前端堆棧中的最後一個元素，這是隊列的第一個元素，如果需要的話。

很明顯，上面的實現是分期付款的O(1)，因爲每個元素被推送到每個堆棧（並從每個堆棧彈出一次）。當然，每次手術都不是O(1)：每隔一段時間pop_front需要相當長的時間。但平均總是正確的。 （推，另一方面，總是O(1)。）

因此，我們可以使min-max隊列中的兩個min-max堆棧，以及解決最大範圍問題的使用。

有了這個提綱，很容易找到一些優化。首先，我們可以將這兩個堆棧存儲在同一個數組中，並且如果我們將後端堆棧向後存儲並與前端堆棧相鄰，那麼我們只需要跟蹤兩個堆棧之間邊界的位置以及彈出操作前端堆棧和將該值推送到後端堆棧的操作僅由移動邊界指針組成。 （但是在min-max堆棧的情況下，我們需要計算mins和maxes）。這導致了一個簡單的循環緩衝區實現，這是一個常見的隊列解決方案。

此外，在移動窗口的情況下，隊列的大小是已知的，所以我們不必處理動態調整大小。而且，在輸入是向量的情況下，我們不需要將元素實際推送到前端堆棧，因爲元素位於輸入中的已知位置，並且我們不需要在堆棧中最小/最大值前面的堆棧。

希望所有足以解釋本C++實現：

#include <algorithm> 
#include <vector> 

using std::min; 
using std::max; 

struct minmax { int min; int max; }; 

int maxrange(const std::vector<int>& v, int n) { 
    int sz = v.size(); 
    n = min(n, sz); 
    if (n <= 1) return 0; 
    // The stack only needs n - 2 elements. So this could be adjusted. 
    minmax* stack = new minmax[n]; 
    int loback, hiback, lofront, hifront; 
    int maxrange = 0; 
    for (int s = n - 1, m = 0; s < sz; ++s, --m) { 
    if (m == 0) { 
     lofront = hifront = v[s]; 
     loback = hiback = v[s - 1]; 
     for (int i = 2; i < n; ++i) { 
     stack[i - 2] = minmax{loback, hiback}; 
     loback = min(loback, v[s - i]); 
     hiback = max(hiback, v[s - i]); 
     } 
     m = n - 1; 
    } else { 
     lofront = min(lofront, v[s]); 
     hifront = max(hifront, v[s]); 
     loback = stack[m-1].min; 
     hiback = stack[m-1].max; 
    } 
    maxrange = max(maxrange, max(hifront, hiback) - min(lofront, loback)); 
    } 
    delete[] stack; 
    return maxrange; 
} 

Answer 3

輸入：

int inp[]={...},n=...; 

1. 創建INT索引陣列用於輸入

   const int N=sizeof(inp)/sizeof(inp[0]); 
   int ix[N]; 
   for (int i=0;i<N;i++) ix[i]=i; 
   

2. 索引排序inp[N]在ix[N]提升（保持inp[N]不變）

   • 所以對於任何i={0,1,2,...,N-2}是(inp[ix[i]]<=inp[ix[i+1]])==true
   • 這可以在O(N*log(N))

3. 現在大小1<n<=N從int i0=0,1,2,...N-n開始的任何子集來完成像這樣做：

   int i1=i0+n-1; // valid indexes for subset are i0<=i<=i1; 
   int min=0,max=0; 
   for (i= 0;i< N;i++) if ((ix[i]>=i0)&&(ix[i]<=i1)) { min=inp[ix[i]]; break; } 
   for (i=N-1;i>=0;i--) if ((ix[i]>=i0)&&(ix[i]<=i1)) { max=inp[ix[i]]; break; } 
   int diff=max-min; 
   

4. 循環子彈3通過所有位置

   • 並找到最大差異...

[注意事項]

• 這是更快更大n但速度較慢較小n
• 所以最好的辦法是使用你的方法，這個方法根據n個大小treshold