将数组通过重复移除任意递增对中的一个元素，最终缩减为单个元素。

---

通过重复移除元素将数组缩减为单个元素，遵循以下标准：

选择索引 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)，因为使用了队列来存储索引。移除元素的顺序会改变最终结果。上述解决方案以递增对中递减的索引顺序移除元素。