目录

python-leetcode-递增的三元子序列

JAY.LIN 收录于 Python

2025-03-12 约 358 字预计阅读 1 分钟

https://bing.ee123.net/img/rand?artid=146167371

目录

python-leetcode-递增的三元子序列

使用 贪心算法 解决这个问题，只需要维护两个最小值 first 和 second ，如果找到了比 second 还大的数，就说明存在递增的三元组。

代码实现

def increasingTriplet(nums):
    first = second = float('inf')

    for num in nums:
        if num <= first:  
            first = num  # 更新最小值
        elif num <= second:  
            second = num  # 更新次小值
        else:  
            return True  # 找到了 third 使得 first < second < third

    return False

# 测试示例
print(increasingTriplet([1, 2, 3, 4, 5]))  # 输出: True
print(increasingTriplet([5, 4, 3, 2, 1]))  # 输出: False
print(increasingTriplet([2, 1, 5, 0, 4, 6]))  # 输出: True

思路解析

初始化 first 和 second 为正无穷大，表示目前找到的最小和次小元素。
遍历数组 ：
- 若 num <= first ，更新 first ，表示找到了更小的数。
- 若 num <= second ，更新 second ，表示找到了更小的次小数。
- 若 num > second ，说明已经找到了 third ，满足 first < second < third ，返回 True 。
如果遍历结束还没返回 True ，则返回 False 。

时间 & 空间复杂度

时间复杂度 ：O(n)（遍历一次数组）
空间复杂度 ：O(1)（只用了两个额外变量）

这种方法高效且不需要额外的存储空间，是最优解！