使用 C++ 替換每個元素為其右側的最小更大元素

為了找到整數陣列右側的最小更大元素，我們需要考慮一個整數陣列。對於每個元素，我們需要找到一個大於當前元素的元素，並且是在我們擁有的所有候選元素中最小的。假設我們有這樣的元素：[5, 23, 65, 31, 76, 32, 87, 23, 76, 32, 88]。

vector<int> arr = {5,23,65,31,76,32,87,23,76,32,88};
solve(arr);

我們可以列出我們的需求，然後思考這些需求以找到解決方案。

我們需要一個數據結構 (ds) 來 -

  • 以排序順序將元素新增到我們的 ds 中（每次我們將某些內容新增到我們的 ds 中時，都會有一個排序順序）

  • 我們需要在我們的排序 ds 中進行 upper_bound 操作，以找到剛剛大於我們當前元素的元素，這將是答案，或者如果不存在這樣的元素，則它將未定義。

我們將從右側遍歷元素。

根據需求，我們選擇了集合 (set) 作為最佳資料結構。

為什麼不是多重集合 (multiset)？我們沒有任何儲存重複元素的需求，所以我們不介意使用多重集合。

注意 - 您可能希望使用 2 個迴圈或二叉搜尋樹，但集合很好地滿足了我們的需求，因此我們將在本文中使用集合。

示例

以下是替換陣列中每個元素為其右側最小更大元素的 C++ 實現 -

#include <iostream>
#include <set>
#include <vector>
using namespace std;
void solve (vector < int >&arr) {
   set < int >s;
   vector < int >ans (arr.size ());
   for (int i = arr.size () - 1; i >= 0; i--) {
      s.insert (arr[i]);
      auto it = s.upper_bound (arr[i]);
      if (it == s.end ())
         arr[i] = -1;
      else
         arr[i] = *it;
   }
}
void printArray (vector < int >&arr) {
   for (int i:arr)
      cout << i << " ";
   cout << "\n";
}
int main () {
   vector < int >arr = { 5, 23, 65, 31, 76, 32, 87, 23, 76, 32, 88 };
   printArray (arr);
   solve (arr);
   printArray (arr);
   return 0;
}

輸出

5 23 65 31 76 32 87 23 76 32 88
23 31 76 32 87 76 88 32 88 88 -1

第 2 個元素 (23) 有一些候選元素 = [65, 31, 76, 32, 87, 76, 32, 88]，它們在 23 的右側並且大於 23。現在我們需要從所有這些元素中選擇最小值，它是 31，所以當前元素的答案變為 31。對於所有其他元素也是如此。所以元素變為

[23 31 76 32 87 76 88 32 88 88 -1]

結論

當我們將陣列的每個元素儲存到我們的集合中時，空間複雜度為 O(n)。我們的方法的時間複雜度為 O(n*log(n))，因為 upper_bound 和插入操作的成本為 log(n)，並且我們對每個元素都執行此操作。總體而言，這個問題純粹是基於資料結構的。考慮到我們的需求，選擇最佳資料結構是我們需要做的全部工作。

更新於: 2022 年 8 月 10 日

169 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

立即開始
廣告