將陣列透過重複移除任意遞增對中的一個元素，最終縮減為單個元素。

---

透過重複移除元素將陣列縮減為單個元素，遵循以下標準：

選擇索引 i 和 j，使得 i < j 且 arr[i] < arr[j]，並將其中一個元素轉換為 0。

問題陳述

給定一個包含正整數的陣列 arr[]。確定是否可以透過重複移除任意遞增對中的一個元素，將陣列縮減為單個元素。如果可能，返回 true 以及所選的索引和被移除元素的索引。

示例 1

輸入

arr[] = {5, 7, 10, 2, 4, 8}

輸出

True
0 1 1
0 2 2
4 5 4
3 5 3
0 5 5

解釋

• **步驟 1** - 選擇索引 0 和 1 處的元素，即 5 和 7。然後移除索引 1 處的元素 7。

• **步驟 2** - 選擇索引 0 和 2 處的元素，即 5 和 10。然後移除索引 2 處的元素 10。

• **步驟 3** - 選擇索引 4 和 5 處的元素，即 4 和 8。然後移除索引 4 處的元素 4。

• **步驟 4** - 選擇索引 3 和 5 處的元素，即 2 和 8。然後移除索引 3 處的元素 2。

• **步驟 5** - 選擇索引 0 和 5 處的元素，即 5 和 8。然後移除索引 5 處的元素 8。

示例 2

輸入

arr[] = {9, 3, 5}

輸出

False

解釋

• **步驟 1** - 選擇索引 1 和 2 處的元素，即 3 和 5。然後移除索引 2 處的元素 5。

• **步驟 2** - 選擇索引 0 和 1 處的元素，即 9 和 3。由於 3 不大於 9，因此陣列無法縮減。

解決方案方法

解決此問題的第一步是首先選擇一組有效的索引。然後，接下來的步驟包括決定刪除哪個元素。如果選擇對中的索引 0 處的元素，則移除非零索引的元素，否則移除較小的元素。重複這些步驟，直到只剩下一個元素。如果只剩下一個元素，則返回 true，否則返回 false。

虛擬碼：

procedure order(a: array of integer, n: integer)
   g <- empty queue of integers
   first <- a[0]
   p <- 0
   for i <- 1 to n - 1
      if a[i] > first
         g.push(i)
   while g.size() > 0 do
      index <- g.front()
      g.pop()
      remove <- index
      while remove > p do
         print remove, " ", index, " ", remove
         remove <- remove - 1
      end while
      print "0 ", index, " ", index
      p <- index
   end while
end procedure
procedure canReduced(arr: array of integer, N: integer)
   if arr[0] > arr[N - 1] then
      print "False"
   else
      print "True"
      order(arr, N)
   end if
end procedure

示例：C++ 實現

以下程式碼使用上述方法來解決問題。

#include <bits/stdc++.h>
using namespace std;

// Function to print the order of indices of converted numbers
void order(int a[], int n){
   // Values of indices with numbers > first index
   queue<int> g;
   int first = a[0];
   // Index of the closest consecutive number to index 0
   int p = 0;
   // Pushing the indices
   for (int i = 1; i < n; i++){
      if (a[i] > first)
         g.push(i);
   }
   // Traverse the queue
   while (g.size() > 0){
      // Index of the closest number > arr[0]
      int index = g.front();
      g.pop();
      int remove = index;
      // Remove elements present in indices [1, remove - 1]
      while (--remove > p) {
         cout << remove << " "
            << index << " "
            << remove << endl;
      }
      cout << 0 << " " << index << " "
      << index << endl;
      // Updating the previous index to index
      p = index;
   }
}
// Function to check if array arr[] can be reduced to single element or not
void canReduced(int arr[], int N){
   // Element can't be reduced to single element
   if (arr[0] > arr[N - 1]){
      cout << "False" << endl;
   }
   else {
      cout << "True" << endl;
      order(arr, N);
   }
}
int main(){
   // Given array arr[]
   int arr[] = {5, 7, 10, 2, 4, 8};
   int N = sizeof(arr) / sizeof(arr[0]);
   canReduced(arr, N);
   return 0;
}

輸出

True
0 1 1
0 2 2
4 5 4
3 5 3
0 5 5

結論

總之，給定的程式碼使用佇列資料結構提供了問題的解決方案。時間複雜度為 O(N)，其中 N 是輸入陣列的長度，因為我們遍歷陣列一次以查詢遞增對，並在每個對上執行一個操作，花費常數時間。空間複雜度也為 O(N)，因為使用了佇列來儲存索引。移除元素的順序會改變最終結果。上述解決方案以遞增對中遞減的索引順序移除元素。