Typescript 编码编年史：增加三元组子序列-js教程-PHP中文网

Typescript 编码编年史：增加三元组子序列

WBOY

发布： 2024-07-17 21:13:42

原创

1121 人浏览过

Typescript Coding Chronicles: Increasing Triplet Subsequence

问题陈述：

给定一个整数数组 nums，如果存在索引三元组 (i, j, k) 且 i

示例1：

输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i

示例2：

输入：nums = [5,4,3,2,1]
输出：假
解释：不存在三元组。

示例3：

输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 有效，因为 nums[3] == 0

限制条件：

1
-2^31

后续：

你能实现一个以 O(n) 时间复杂度和 O(1) 空间复杂度运行的解决方案吗？

初步思考过程：

为了有效地解决这个问题，我们需要跟踪迄今为止遇到的最小和第二小的值。如果我们找到大于第二小的值的第三个值，那么我们就找到了递增三元组。

基本解决方案（暴力）：

暴力解决方案涉及检查所有可能的三元组，看看是否存在满足条件 i

代码：

function increasingTripletBruteForce(nums: number[]): boolean {
    const n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] < nums[j] && nums[j] < nums[k]) {
                    return true;
                }
            }
        }
    }
    return false;
}

登录后复制

时间复杂度分析：

时间复杂度： O(n^3)，其中 n 是数组的长度。这是因为我们正在检查所有可能的三元组。
空间复杂度： O(1)，因为我们没有使用任何额外的空间。

限制：

暴力解决方案效率不高，不适合大输入。

优化方案：

优化的解决方案涉及迭代数组，同时维护两个变量，第一和第二，它们代表迄今为止遇到的最小和第二小的值。如果我们找到大于秒的值，则返回 true。

代码：

function increasingTriplet(nums: number[]): boolean {
    let first = Infinity;
    let second = Infinity;

    for (let num of nums) {
        if (num <= first) {
            first = num; // smallest value
        } else if (num <= second) {
            second = num; // second smallest value
        } else {
            return true; // found a value greater than second smallest, thus an increasing triplet exists
        }
    }

    return false;
}

登录后复制

时间复杂度分析：

时间复杂度： O(n)，其中 n 是数组的长度。我们迭代数组一次。
空间复杂度： O(1)，因为我们仅使用恒定量的额外空间。

基本解决方案的改进：

该解决方案以线性时间运行并使用恒定空间，使其对于给定的约束而言是最佳的。

边缘情况和测试：

边缘情况：

数组按降序排列。
该数组恰好包含三个按升序排列的元素。
数组有大量元素且没有递增的三元组。
数组包含重复项。

测试用例：

console.log(increasingTripletBruteForce([1,2,3,4,5])); // true
console.log(increasingTripletBruteForce([5,4,3,2,1])); // false
console.log(increasingTripletBruteForce([2,1,5,0,4,6])); // true
console.log(increasingTripletBruteForce([1,1,1,1,1])); // false
console.log(increasingTripletBruteForce([1,2])); // false
console.log(increasingTripletBruteForce([1,2,3])); // true
console.log(increasingTripletBruteForce([1,5,0,4,1,3])); // true

console.log(increasingTriplet([1,2,3,4,5])); // true
console.log(increasingTriplet([5,4,3,2,1])); // false
console.log(increasingTriplet([2,1,5,0,4,6])); // true
console.log(increasingTriplet([1,1,1,1,1])); // false
console.log(increasingTriplet([1,2])); // false
console.log(increasingTriplet([1,2,3])); // true
console.log(increasingTriplet([1,5,0,4,1,3])); // true

登录后复制