核心内容摘要
当数学课代表的泪水，浸湿了“不能再生”的数字游戏
题目链接
问题描述给定一个整数数组nums判断是否存在长度为3的递增子序列即是否存在下标i j k使得nums[i] nums[j] nums[k]。
存在则返回true否则返回false。
核心解法解法1动态规划DP思路计算数组的**最长递增子序列LIS**的长度若长度 ≥ 3则说明存在符合要求的子序列。
实现逻辑定义dp[i]表示以nums[i]结尾的最长递增子序列的长度。
对每个i遍历所有j i若nums[j] nums[i]则dp[i] max(dp[i], dp[j]
。
遍历dp数组若存在值 ≥ 3直接返回true。
复杂度时间复杂度O(n²)空间复杂度O(n)需存储dp数组。
解法2贪心算法思路用两个变量a、b分别记录长度为1和长度为2的递增子序列的最小末尾值遍历数组时更新这两个变量一旦找到比b大的元素说明存在长度为3的递增子序列。
实现逻辑以示例[2,1,5,0,4,6]为例初始化a ∞b ∞。
遍历每个元素x若x ≤ a→ 更新a x保持长度1的子序列末尾最小若a x ≤ b→ 更新b x保持长度2的子序列末尾最小若x b→ 说明存在a b x即长度为3的递增子序列直接返回true。
遍历结束未找到则返回false。
复杂度时间复杂度O(n)仅需一次遍历空间复杂度O(
仅用两个变量是更优的解法。
知识点
总结问题本质该问题是「最长递增子序列LIS」的特例只需判断 LIS 长度是否 ≥ 3。
算法对比动态规划适用于需要完整计算 LIS 长度的场景但时间复杂度较高贪心解法针对「判断是否存在长度为3的递增子序列」做了优化时间、空间效率更优。
贪心策略的核心维护最小的可能末尾值让后续更容易找到更长的递增子序列从而提升效率。