LeetCode 334. 递增的三元子序列 题解题目描述给定一个整数数组nums判断数组中是否存在下标满足 i j k的三元子序列使得nums[i] nums[j] nums[k]。若存在满足条件的三元组返回true否则返回false。补充说明子序列不要求原数组中的元素连续仅需保证元素的下标顺序与原数组一致即可。前置分析在设计解法前先梳理本题的核心特征明确解题的约束条件与优化方向存在性判断仅需验证是否存在一组符合条件的三元组无需枚举所有解可提前终止遍历下标顺序约束ijk的要求天然适配单次线性遍历无需额外处理下标关系固定长度目标目标子序列长度固定为3无需适配通用长度的递增子序列问题无全局统计需求仅需维护局部状态变量无需存储全量数据空间复杂度可优化至常数级。结合以上特征排除暴力枚举时间复杂度O(n3)O(n^3)O(n3)效率过低、动态规划空间复杂度更高冗余计算等方案贪心算法是本题的最优选择。算法选择依据贪心算法的核心思想是在每一步选择中都采取当前状态下的局部最优策略最终推导出全局的可行解与本题的特征高度匹配仅需判断可行性无需计算最优解数值贪心策略可直接满足需求针对长度为3的递增子序列仅需维护两个局部变量即可记录状态空间开销极低线性遍历的过程中一旦找到符合条件的第三个元素可立即返回结果无需遍历完整数组下标顺序约束与贪心算法的单向遍历逻辑完全契合无逻辑冲突。解题思路基于贪心策略我们通过维护两个关键变量持续更新数组遍历过程中的局部最小值逐步缩小寻找目标元素的范围定义变量first记录遍历过程中当前遇到的最小值作为三元组的第一个候选元素定义变量second记录在大于 first的前提下当前遇到的最小值作为三元组的第二个候选元素遍历数组中的每一个元素依次进行判断若当前元素小于等于first更新first为当前元素替换更小的首候选值为后续寻找递增元素创造更多可能若当前元素大于first且小于等于second更新second为当前元素替换更小的次候选值降低找到第三个递增元素的门槛若当前元素大于second说明已找到满足nums[i]nums[j]nums[k]的三元组直接返回true若完整遍历数组后仍未找到符合条件的元素返回false。边界处理数组长度小于3时无法构成三元子序列可直接返回false无需执行后续逻辑。代码实现本题采用 C 语言实现代码中添加了详细注释兼顾可读性与执行效率usingnamespacestd;classSolution{public:boolincreasingTriplet(vectorintnums){intlennums.size();// 边界条件数组长度不足3直接返回falseif(len3){returnfalse;}// 初始化两个候选值为整数最大值保证首次遍历能正常更新intfirstINT_MAX;intsecondINT_MAX;for(intnum:nums){if(numfirst){// 更新最小的第一个候选元素firstnum;}elseif(numsecond){// 更新比first大的最小第二个候选元素secondnum;}else{// 找到大于second的元素满足递增三元子序列条件returntrue;}}// 遍历完成未找到符合条件的三元组returnfalse;}};复杂度分析时间复杂度算法仅对数组执行一次线性遍历遍历过程中所有判断与赋值操作均为常数级时间复杂度因此总时间复杂度为O(n)O(n)O(n)其中nnn为数组nums的长度。空间复杂度算法仅使用了len、first、second三个常数级变量未开辟与输入规模相关的额外存储空间因此空间复杂度为O(1)O(1)O(1)。总结本题利用贪心算法的局部最优特性仅通过两个变量即可完成状态维护在时间和空间复杂度上均达到最优解题核心是持续缩小候选值的阈值用更小的候选值提升后续匹配成功率同时利用存在性判断的特性提前终止遍历