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

php中文网 2024-10-15 11:13:04

问题陈述：

给定一个整数数组 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 



<h3>
  
  
  时间复杂度分析：
</h3>

时间复杂度： 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 



<h3>
  
  
  时间复杂度分析：
</h3>

时间复杂度： 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