找出O（n）中給定數組的每個子陣列的每對最小整數？

我遇到問題。 給定一個數組，找到所有可能的子陣列中的最小整數和次小整數，其中子陣列是原始陣列的連續子集。例如，考慮一個數組A = [5,6,1,2,9,3]。顯然子陣列的大小至少爲2，所以我們有總共（n）*（n + 1）/ 2 - n個子陣列。（從總數中減去n個大小爲1的子陣列）。這是一個直接的O（n^2）解決方案，檢查每個子陣列並記錄所需的整數。但我認爲它可以在O（n）中使用堆棧完成。但我無法直觀地使用它來達到最佳解決方案。任何幫助，建議，方向將不勝感激。找出O（n）中給定數組的每個子陣列的每對最小整數？

來源

2017-09-26 farzi_engineer

是的，它可以在O（n）完成，這個想法是用來解決這個question。

For each int i in the array A 
    while stack is nonempty 
     // current min is stack.top() and A[i] 
     if i is less than the top of the stack, pop the stack 
     otherwise break the while loop 
    If stack is non empty 
     // current min is stack.top() and A[i] 
    push i onto stack

的基本想法是，如果你在你的堆棧值B，你遇到一個值c哪一個較小，則B不能形成最小配對什麼C的右側。所以一旦你產生了這對（b，c），你可以安全地處理b（你已經處理了可能的配對）。

檢查出來的online compiler

來源

2017-09-26 11:55:29 marvel308

雖然我很欣賞的答案，但我缺乏這種算法背後的直覺。是的，我也通過討論這個問題的論壇，他們提到了相同的算法。 **如果你的堆棧中有一個值b，並且你遇到一個較小的值c，那麼b不能與c右邊的任何東西形成一個最小的對。。 –

，因爲在這種情況下，c將在答案中而不是b中。假設我有1 5 3 4，在這種情況下，5將不會對4的權利作出貢獻 – marvel308

找出O（n）中給定數組的每個子陣列的每對最小整數？

回答

相關問題