有没有一种有效的方法来找到长度为 3 的子序列，其中第一个是最低的，第二个是最大的，最后一个在该范围内？

Question

例如，给定列表 [5, 9, 1, 2, 7, 8]，算法应该找到诸如 [5, 9, 7] 或 [5, 9, 8] 之类的子序列。

我需要算法高效。一种方法可能涉及在迭代列表时跟踪最大值和最小值。每当一个数字落在当前最大值和最小值之间时，它就是一个潜在的候选者。然而，这种方法在某些情况下可能会失败，比如：

考虑列表 [5,8,10,2,4]。该算法可能会建议 [2, 10, 4] 作为解决方案，但它违反了最低值必须先于最高值的限制。

您知道有效的解决方案吗？谢谢你。

Answer 1

您可以使用这种方法：

• 从左向右迭代时获取“运行”最小值，并将它们存储在数组中

  min

• 从从右到左迭代时，获取“运行”最大值以及被当前运行最大值取代的前一个运行最大值，并且如果在索引

  i

  处，我们对这些运行最大值有两个不同的值，并且较小的一个大于

  min[i]

  ，我们找到了一个合适的三元组。

可运行 JavaScript 片段中的实现：

function getTriplet(arr) {
    const n = arr.length;
    // Collect running minimum:
    const min = [...arr]; // Copy
    for (let i = 1; i < n; i++) {
        min[i] = Math.min(min[i-1], min[i]);
    }
    // Get running maximum and "older" second-to-maximum in reverse traversal
    let max = arr[n-1];
    let mid = arr[n-1]; // Not a valid candidate yet!
    for (let i = n - 2; i > 0; i--) {
        if (arr[i] > max) {
            mid = max; // The second-to-maximum takes the previous maximum
            max = arr[i];
        }
        if (min[i] < mid && mid < max) { // BINGO
            return [min[i], max, mid];
        }
    }
}

// Test case 1:
const arr = [5, 9, 1, 2, 7, 8];
console.log(getTriplet(arr)); // 5 9 8
// Test case 2:
const arr2 = [5, 8, 10, 2, 4];
console.log(getTriplet(arr2)); // undefined: no solution