高效求解数组中满足a<b>c的子序列三元组最小和问题

给定长度为n的数值数组，寻找满足以下条件的长度为3的子序列sub：

• 子序列元素索引满足i<j<k
• 值大小满足sub[0] < sub[1] > sub[2]（即中间元素为峰值）
  要求返回所有符合条件三元组的元素和的最小值。

示例：对于数组[3,4,5,1,2,3,1]，符合条件的最小和三元组为[1,2,1]，和为1+2+1=4
约束条件：数组长度最大为100000，单个元素取值范围为1~1e9

你当前使用的三层嵌套循环实现时间复杂度为O(n³)，在n=1e5的规模下完全无法运行，需要优化到线性级别。

核心思路是固定中间峰值位置，避免无意义的多层遍历：
对于每个位置j作为三元组的中间峰值，要得到以j为峰值的最小和三元组，只需要找到：

1. j左侧所有比arr[j]小的元素中的最小值
2. j右侧所有比arr[j]小的元素中的最小值
   三者相加就是以j为峰值的最小可能和。遍历所有位置j取全局最小值即可。

这里有一个非常关键的简化逻辑：

对于位置j左侧的元素，如果左侧所有元素的最小值都大于等于arr[j]，说明左侧没有符合要求的元素；如果左侧最小值小于arr[j]，那这个最小值就是我们要找的左侧最小合法值——没有比它更小的数能满足小于arr[j]的要求了。

右侧的逻辑完全一致。
基于这个逻辑，我们不需要任何复杂的有序数据结构，只需要两次线性遍历就能预处理出所有需要的信息，整体时间复杂度O(n)，空间复杂度O(n)，完全可以支撑1e5规模的数据。

• 预处理右侧最小值数组rightMin：从数组末尾向左遍历，维护当前遍历过的元素（即当前位置右侧所有元素）的最小值，存入数组对应位置。如果右侧没有比当前元素小的值，存为无穷大。
• 从数组头部向右遍历，动态维护当前遍历过的元素（即当前位置左侧所有元素）的最小值leftMin。
• 对于每个遍历到的位置j，如果leftMin < arr[j]且rightMin[j] < arr[j]，计算三者之和，更新全局最小结果。
• 遍历完成后返回全局最小结果即可。

public long process(List<Integer> list) {
    int n = list.size();
    if (n < 3) {
        return Long.MAX_VALUE;
    }
    long[] rightMin = new long[n];
    long currentMin = Long.MAX_VALUE;
    // 从右往左预处理右侧最小值
    for (int j = n-1; j >=0; j--) {
        rightMin[j] = currentMin;
        if (list.get(j) < currentMin) {
            currentMin = list.get(j);
        }
    }
    long output = Long.MAX_VALUE;
    long leftMin = Long.MAX_VALUE;
    // 从左往右遍历，维护左侧最小值，计算结果
    for (int j = 0; j < n; j++) {
        int val = list.get(j);
        // 左右都有比当前值小的元素，才能作为峰值
        if (leftMin < val && rightMin[j] < val) {
            long sum = leftMin + val + rightMin[j];
            if (sum < output) {
                output = sum;
            }
        }
        // 更新左侧最小值
        if (val < leftMin) {
            leftMin = val;
        }
    }
    return output;
}

• 时间复杂度：O(n)，仅做两次从头到尾的线性遍历，每个元素仅处理常数次
• 空间复杂度：O(n)，仅需要一个长度为n的数组存储右侧最小值，如果允许修改原数组可以进一步优化到O(1)额外空间，无复杂数据结构开销。

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