给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。
十分钟写出来的费时费空间解法:
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: n = len(nums) if n < 3: return False ## DP1 动态规划,定义第i个值为在这个数左边含这个数能达到的最小值 dp1 = [nums[0]] * n for i in range(1,n): dp1[i] = min(dp1[i-1], nums[i]) ## DP2 动态规划,定义第i个值为在这个数右边含这个数能达到的最大值 dp2 = [nums[-1]] * n for i in range(n-2,-1,-1): dp2[i] = max(dp2[i+1], nums[i]) for i in range(n): if nums[i] > dp1[i] and nums[i] < dp2[i]: return True return False
执行用时:224 ms, 在所有 Python3 提交中击败了7.07%的用户
内存消耗:27.5 MB, 在所有 Python3 提交中击败了5.12%的用户
其实也就是官方标答的双向遍历法:
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: n = len(nums) if n < 3: return False leftMin = [0] * n leftMin[0] = nums[0] for i in range(1, n): leftMin[i] = min(leftMin[i - 1], nums[i]) rightMax = [0] * n rightMax[n - 1] = nums[n - 1] for i in range(n - 2, -1, -1): rightMax[i] = max(rightMax[i + 1], nums[i]) for i in range(1, n - 1): if leftMin[i - 1] < nums[i] < rightMax[i + 1]: return True return False
贪心算法:
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: n = len(nums) if n < 3: return False first, second = nums[0], float('inf') for i in range(1, n): num = nums[i] if num > second: return True if num > first: second = num else: first = num return False
贪心算法比较巧的一点就是,出现第三个数的情况。基于第三个数一定会比第二个数小,所以可以取缔第二个数或者第一个数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/increasing-triplet-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。