难度: Medium
给你一个整数数组 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 * 105-231 <= nums[i] <= 231 - 1进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？
运行时间: 41 ms
内存: 34.9 MB
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
min_val = float('inf') # 初始化最小值为正无穷大
second_min_val = float('inf') # 初始化第二小值为正无穷大
for num in nums:
if num <= min_val:
min_val = num # 更新最小值
elif num <= second_min_val:
second_min_val = num # 更新第二小值
else:
return True # 找到了递增的三元组
return False # 没有找到递增的三元组
该题解使用了贪心算法的思路。我们维护两个变量min_val和second_min_val，分别表示遍历过程中的最小值和第二小值。遍历数组，如果当前元素小于等于min_val，则更新min_val；如果当前元素大于min_val但小于等于second_min_val，则更新second_min_val；如果当前元素大于second_min_val，说明找到了一个递增的三元组，返回True。如果遍历完数组没有找到递增的三元组，返回False。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
min_val = float('inf') # 初始化最小值为正无穷大
second_min_val = float('inf') # 初始化第二小值为正无穷大
for num in nums:
if num <= min_val:
min_val = num # 更新最小值
elif num <= second_min_val:
second_min_val = num # 更新第二小值
else:
return True # 找到了递增的三元组
return False # 没有找到递增的三元组
是的，该算法在找到第一个满足条件的三元组后会立即返回True并停止搜索。这是因为题目只需要判断是否至少存在一个递增的三元子序列，而不需要找出所有可能的三元组。如果数组中存在多个满足条件的三元组，该算法仍然在找到第一个后就停止处理，因此不会有不同的处理方式。
当找到一个大于second_min_val的数字时，可以确信存在一个递增的三元子序列，因为按照算法逻辑，second_min_val只会在之前找到一个更小的min_val之后才会被更新。这意味着已经存在至少两个数min_val和second_min_val，且min_val < second_min_val。因此，当找到第三个数大于second_min_val时，就确定了一个递增的三元子序列(min_val, second_min_val, num)。在这种逻辑下，second_min_val确实是递增序列中的第二个元素。
使用float('inf')进行初始化是为了确保任何数组中的第一个元素都能更新min_val，而第二个大于min_val的元素能更新second_min_val。在Python中，float('inf')表示一个比任何其他浮点数都大的值。因此，即使数组中包含非常大的数值，只要这些数值是有限的，算法仍然有效。对于非常小的数值，同样有效，因为无论数值多么小，都小于float('inf')。
如果输入数组nums为空或只有一个或两个元素，算法会返回False。这是因为至少需要三个元素才能形成一个递增的三元子序列。算法在这种情况下返回False是与预期行为一致的，因为不存在足够的元素来形成所需的序列。