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

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

WBOY

发布： 2024-07-12 10:04:23

转载

400人浏览过

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

问题陈述：

给定一个整数数组 nums，如果存在三个索引 (i, j, k)，使得 i < j < k 和 nums[i] < nums[j] < nums[k]，则返回 true。如果不存在这样的索引，则返回 false。

示例1：

输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都是有效的。

示例2：

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

示例3：

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

限制条件：

1 <= nums.length <= 5 * 10^5
-2^31 <= nums[i] <= 2^31 - 1

跟进：

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

初步思考过程：

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

基本解决方案（暴力）：

暴力解决方案涉及检查所有可能的三元组，看看是否存在满足条件 i < j < k 和 nums[i] < nums[j] < nums[k] 的三元组。这种方法的时间复杂度为 o(n^3)，对于大输入量来说效率不高。

代码：

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。

AI图像编辑器

使用文本提示编辑、变换和增强照片

查看详情

代码：

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

登录后复制