c++ - 查找数组中的对数，使得数组中存在的这些对之间的所有元素都小于对本身

Question

我们有一个不同的正整数数组。我们必须找到数组中的对数，使得数组中这些对之间的所有元素都小于对元素本身。

例如，如果数组是 [7 3 2 1 4 6 5]，那么输出将为 10，因为 (7,4) 、 (7,6) 、 (3,4) 、 (2,4) 之间的所有整数在数组中小于提到的对，并且考虑到它们之间没有元素的 6 个相邻对，即。(size(array) - 1)，因此 4 + 6 = 10。类似地，对于 [10 3 4 8 6]，输出为 6，对于 [2 80 4 32]，输出为 4。

我能够使用效率不高的蛮力方法（2个嵌套循环）以及使用具有O（N）（时间和空间）中的下一个/上一个更大元素的概念的堆栈来实现结果。然而，我正在寻找一种更有效或更快的方法（可能只是使用指针，或事先操作数组）而不使用任何额外的 DS/空间，即 O(N) 时间和 O(1) 空间。

我使用堆栈方法附加了我的代码：

#include <iostream>
#include <stack>
using namespace std;

int main(){
   int n, pairs = 0;
   cin >> n;
   int arr[n];
   for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    stack <int> s1, s2;
    
    int i = 1;
    s1.push(arr[0]);
    while (i < n) {
        if (!s1.empty() and arr[i] > s1.top()) {
            s1.pop();
            pairs++;
        }
        else {
            s1.push(arr[i]);
            i++;
        }
            
    }
    int j = n - 2;
    s2.push(arr[n-1]);
    while(j > -1) {
        if(!s2.empty() and arr[j] > s2.top()) {
            s2.pop();
            pairs++;
        }
        else {
            s2.push(arr[j]);
            j--;
        }
    }

    cout << pairs;
}

标签： c++arraysalgorithmpointersoptimization