面试必看：递增的三元子序列-洪萨配资

LeetCode 334. 递增的三元子序列题解

题目描述

给定一个整数数组nums，判断数组中是否存在下标满足 i < j < k的三元子序列，使得nums[i] < nums[j] < nums[k]。若存在满足条件的三元组，返回true，否则返回false。

补充说明：子序列不要求原数组中的元素连续，仅需保证元素的下标顺序与原数组一致即可。

前置分析

在设计解法前，先梳理本题的核心特征，明确解题的约束条件与优化方向：

存在性判断：仅需验证是否存在一组符合条件的三元组，无需枚举所有解，可提前终止遍历；
下标顺序约束：i<j<k的要求天然适配单次线性遍历，无需额外处理下标关系；
固定长度目标：目标子序列长度固定为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(vector<int>&nums){intlen=nums.size();// 边界条件：数组长度不足3，直接返回falseif(len<3){returnfalse;}// 初始化两个候选值为整数最大值，保证首次遍历能正常更新intfirst=INT_MAX;intsecond=INT_MAX;for(intnum:nums){if(num<=first){// 更新最小的第一个候选元素first=num;}elseif(num<=second){// 更新比first大的最小第二个候选元素second=num;}else{// 找到大于second的元素，满足递增三元子序列条件returntrue;}}// 遍历完成未找到符合条件的三元组returnfalse;}};