LC334. 递增的三元组

LC334. 递增的三元组

题目描述

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。 如果存在这样的三元组下标 (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] 输出：false 解释：不存在满足题意的三元组 示例 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) 的解决方案吗？

题目解析

解题思路

本题要求判断数组中是否存在长度为3的递增子序列，且要求时间复杂度O(n)、空间复杂度O(1)。参考代码采用贪心思想，通过维护两个变量first和second来记录当前已找到的最优递增二元组。

核心思路是：遍历数组时，始终维护当前最小的两个递增数（first < second），并不断尝试用更小的值更新它们，使得后续更容易找到比second更大的第三个数。这种策略保证了只要存在递增三元组，就一定能被检测到。

关键步骤

1. 初始化：将first和second均设为无穷大（float('inf')），表示尚未找到有效值。

2. 遍历每个数`third`：

• 若third > second：说明找到了比second更大的数，即存在first < second < third，直接返回True。
• 若third <= first：用third更新first，因为更小的first能为后续second提供更大的选择空间。
• 否则（first < third <= second）：用third更新second，因为更小的second能为后续third提供更大的选择空间。

3. 遍历结束：若未提前返回，则不存在递增三元组，返回False。

复杂度分析

• 时间复杂度：O(n)，只需一次线性遍历。
• 空间复杂度：O(1)，仅使用两个额外变量。

示意图（关键步骤）

初始: first=∞, second=∞

遍历 [2,1,5,0,4,6]:
  third=2: 2<=first → first=2
  third=1: 1<=first → first=1
  third=5: 1<5, 5>second(∞) → second=5
  third=0: 0<=first(1) → first=0
  third=4: 0<4<=5 → second=4
  third=6: 6>second(4) → return True