求数组中间元素均小于两端的配对数 如何实现O(1)空间O(N)解法

问题描述 #

给定由互不相同正整数组成的数组，统计满足如下条件的元素配对数量：配对的两个元素之间的所有数组元素值，均小于这两个配对元素本身。

示例说明 #

• 数组[7, 3, 2, 1, 4, 6, 5]输出结果为10：其中符合条件的非相邻配对共4个，分别为(7,4)、(7,6)、(3,4)、(2,4)；加上6个无中间元素的相邻配对（数量等于数组长度减1），总计数为4+6=10。
• 数组[10, 3, 4, 8, 6]输出结果为6。
• 数组[2, 80, 4, 32]输出结果为4。

已有实现方案 #

目前可通过两种方案实现需求：

• 暴力解法：采用两层循环遍历统计，运行效率较低。
• 栈解法：基于Next/Previous Greater Element（下一个/上一个更大元素）逻辑实现，时间复杂度与空间复杂度均为O(N)。

优化需求 #

希望找到更高效的实现方案，要求不使用额外数据结构，达到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;
}

内容的提问来源于stack exchange，提问作者Joshin Rexy