分享一种非递归的方法以及一种贪心的方法优第一种是自己想的方法一思路先找最大数A如果最大数左边没有两个数删除最大数A。继续寻找最大数A再找最大数左边最大的数B如果最大数B在最左边删除这个数B。如果不在最左边说明该数列存在递增的三元子序列。解题过程这段代码的思路是反复裁剪列表试图找到三个呈严格递增趋势的数。具体逻辑如下持续循环直到列表长度不足 3每次循环先做快速否决如果用集合去重后不同元素少于 3 个直接返回 False因为严格递增需要至少三个不同的数。定位当前列表的最大值找出最大值及其第一次出现的位置索引 max_index。根据最大值的位置分情况处理如果最大值左边至少有两个元素 (max_index 1)在最大值左边的切片中再找一个最大值并获取该值在整个当前列表中第一次出现的位置 max_index_left。若 max_index_left 0说明这个“左边最大值”不在列表最开头它的左边至少还有一个元素。这时认为已经找到一组候选三元组最左侧有数 ≤ 左边最大值加上左边最大值再加上全局最大值直接跳出循环准备返回 True。若 max_index_left 0左边最大值正好在列表最左端无法在它左边找到更小的数因此当前的最大值无法与左边的数构成有效三元组。于是删除列表的第一个元素开启下一轮循环。如果最大值左边不足两个元素 (max_index 1)当前最大值无法作为三元组的结尾直接删除这个最大值继续循环。最终判断循环可能因为 break 退出找到了结构也可能因为列表被删到不足 3 个元素而自然结束。如果退出后列表长度仍 ≥ 3说明找到了符合条件的结构返回 True否则返回 False。Python代码class Solution: def increasingTriplet(self, nums: List[int]) - bool: while len(nums) 3: if len(set(nums))3: return False max_index, max_num nums.index(max(nums)), max(nums) if max_index 1: max_index_left, max_num_left nums.index(max(nums[:max_index])), max( nums[:max_index]) if max_index_left 0: break else: del nums[0] else: del nums[max_index] if len(nums) 3: return True else: return False方法二贪心解法、好思路解释我们只需要知道是否存在递增的三个数不需要输出它们具体是谁。维护两个变量first当前遇到的最小值second在某个first之后出现的大于first的最小值遍历数组时对于每个数x若x first更新first x。first总是尽可能小为后面的second留出更大空间。若x first且x second更新second x。second表示在某个first后出现的、比first大的最小数。若x second说明存在一个数first second x返回True。如果遍历完都没找到返回False。Python代码时间n空间1class Solution: def increasingTriplet(self, nums: List[int]) - bool: first float(inf) second float(inf) for x in nums: if x first: # 小于等于 first更新 first尽量小 first x elif x second: # 大于 first 但小于等于 second更新 second second x else: # x second找到递增三元组 return True return False
力扣334.递增的三元子序列
分享一种非递归的方法以及一种贪心的方法优第一种是自己想的方法一思路先找最大数A如果最大数左边没有两个数删除最大数A。继续寻找最大数A再找最大数左边最大的数B如果最大数B在最左边删除这个数B。如果不在最左边说明该数列存在递增的三元子序列。解题过程这段代码的思路是反复裁剪列表试图找到三个呈严格递增趋势的数。具体逻辑如下持续循环直到列表长度不足 3每次循环先做快速否决如果用集合去重后不同元素少于 3 个直接返回 False因为严格递增需要至少三个不同的数。定位当前列表的最大值找出最大值及其第一次出现的位置索引 max_index。根据最大值的位置分情况处理如果最大值左边至少有两个元素 (max_index 1)在最大值左边的切片中再找一个最大值并获取该值在整个当前列表中第一次出现的位置 max_index_left。若 max_index_left 0说明这个“左边最大值”不在列表最开头它的左边至少还有一个元素。这时认为已经找到一组候选三元组最左侧有数 ≤ 左边最大值加上左边最大值再加上全局最大值直接跳出循环准备返回 True。若 max_index_left 0左边最大值正好在列表最左端无法在它左边找到更小的数因此当前的最大值无法与左边的数构成有效三元组。于是删除列表的第一个元素开启下一轮循环。如果最大值左边不足两个元素 (max_index 1)当前最大值无法作为三元组的结尾直接删除这个最大值继续循环。最终判断循环可能因为 break 退出找到了结构也可能因为列表被删到不足 3 个元素而自然结束。如果退出后列表长度仍 ≥ 3说明找到了符合条件的结构返回 True否则返回 False。Python代码class Solution: def increasingTriplet(self, nums: List[int]) - bool: while len(nums) 3: if len(set(nums))3: return False max_index, max_num nums.index(max(nums)), max(nums) if max_index 1: max_index_left, max_num_left nums.index(max(nums[:max_index])), max( nums[:max_index]) if max_index_left 0: break else: del nums[0] else: del nums[max_index] if len(nums) 3: return True else: return False方法二贪心解法、好思路解释我们只需要知道是否存在递增的三个数不需要输出它们具体是谁。维护两个变量first当前遇到的最小值second在某个first之后出现的大于first的最小值遍历数组时对于每个数x若x first更新first x。first总是尽可能小为后面的second留出更大空间。若x first且x second更新second x。second表示在某个first后出现的、比first大的最小数。若x second说明存在一个数first second x返回True。如果遍历完都没找到返回False。Python代码时间n空间1class Solution: def increasingTriplet(self, nums: List[int]) - bool: first float(inf) second float(inf) for x in nums: if x first: # 小于等于 first更新 first尽量小 first x elif x second: # 大于 first 但小于等于 second更新 second second x else: # x second找到递增三元组 return True return False
