如何优化有序三元组计数算法以降低时间复杂度、提升性能？

问题描述 #

给定一个元素无序且无重复的int数组nums，长度范围为[3,20000]，元素取值范围为[1,100000]。若三元组(a,b,c)满足0≤a<b<c<nums.length()，且nums[a]≥nums[b]≥nums[c]或nums[a]≤nums[b]≤nums[c]，则称其为good combination。需快速统计数组中此类组合的数量。

用例 #

• 用例1：输入[1,2,3]，输出1
  说明：仅存在一个good combination [1,2,3]
• 用例2：输入[1,2,3,4]，输出4
  说明：存在四个good combination，分别为[1,2,3]、[1,2,4]、[1,3,4]、[2,3,4]

现有实现 #

最初采用三重循环实现，时间复杂度为O(n³)，性能极差：

public static long run(int[] params) {
    long count = 0;
    for (int i = 0; i < params.length - 2; i++) {
        for (int j = i + 1; j < params.length - 1; j++) {
            for (int k = j + 1; k < params.length; k++) {
                if (params[i] <= params[j] && params[j] <= params[k] ||
                        params[i] >= params[j] && params[j] >= params[k]) {
                    count++;
                }
            }
        }
    }
    return count;
}

后续优化为固定中间元素统计左右元素的方式，但时间复杂度仍为O(n²)：

public static long run(int[] params) {
    int n = params.length;
    long count = 0;
    for (int j = 1; j < n - 1; j++) {
        int leftLess = 0, leftMore = 0, rightLess = 0, rightMore = 0;
        for (int i = 0; i < j; i++) {
            if (params[i] <= params[j]) {
                leftLess++;
            } else {
                leftMore++;
            }
        }
        for (int k = j + 1; k < n; k++) {
            if (params[k] >= params[j]) {
                rightMore++;
            } else {
                rightLess++;
            }
        }
        count += leftLess * rightMore + leftMore * rightLess;
    }
    return count;
}

优化需求 #

需要进一步优化该算法，降低时间复杂度，提升运行性能。

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