这题我印象太深了第一次在LeetCode上刷到“递增的三元子序列”时我用动态规划叠了三个嵌套循环AC是AC了跑起来跟老牛拉车似的。后来看了题解里那个只用两个变量的写法愣了半天才想明白真是后脑勺一拍原来子序列问题也能贪心成这副德行。今天这篇就把这道题彻底讲透从最直觉的暴力解法开始然后是DP最后落到那个空间常数级别的哨兵写法每一步都说明白为什么。每天学习一点算法递增的三元子序列这题是个典型的中等难度问题题干特别短给定一个数组判断是否存在下标 i j k且 nums[i] nums[j] nums[k]。也就是说能不能在数组里按原顺序挑出三个数让它们的数值严格递增。注意三个字关键点要求的是下标递增不是要求连续也不是要求值相邻。也就是说哪怕三个数中间隔着十万八千里只要从左往右能依次找到这样三个数就算成立。这道题非常适合用来训练三个能力边界条件处理、状态压缩的思维惯性、以及“一个变量参与多次计算时怎么保证语义不错乱”。很多人死在明明存在三元组却返回 false或者反过来数组里根本没有严格递增的三元组却误判成 true。这两种问题我都见过踩坑的原因不外乎那两个一个是忽略“等于不算递增”另一个是把数组中间的极小值直接当成了第一棒。1. 这题到底在问什么一点就透的题目还原1.1 别被“子序列”三个字唬住算法题里一出现“子序列”很多人第一反应就是最长递增子序列LIS那一套动态规划。这确实不算错但它会把人往重武器的方向带。要知道子序列的本质是“可以跳着选但不能改变相对顺序”这跟连续子数组有本质区别。连续子数组用滑动窗口就好子序列往往需要维护某种前缀信息。这道题只需要长度是3所以完全不需要开一个数组去记录 dp[i] 表示以 i 结尾的最长递增子序列长度。你只需要知道一件事在扫描到某个位置时当前出现过的“最小值”以及“在某个最小值之后出现过的第二小值”。这两个值一拼就是三元组的前两棒。1.2 两个容易踩的解读坑第一个坑递增到底是严格递增还是非严格递增。题干写的是nums[i] nums[j] nums[k]所以是严格递增。也就是说如果数组中只有[1, 1, 1]答案必须是 false因为根本没有“严格递增”的三元组。很多人在代码里写成处理就会把相等的情况也判定成 true。第二个坑下标是“位置顺序”不是“数值顺序”。有人会想当然地先去排序然后看排序后的数组前三个数是不是递增。这完全跑偏因为排序会破坏原数组的先后关系。举个反例[4, 2, 1, 3]排序后是[1, 2, 3]看着有递增三元组但原数组里 1 的下标比 3 靠前吗不是1 在最后3 在倒数第二位它们没法按原顺序组成三元组所以这道题答案是 false。必须先理解清楚这个前提后面的算法才有意义。2. 暴力、动态规划、贪心三条路的取舍2.1 暴力枚举能想清楚问题的底线方案拿到这道题脑子最直白的做法就是套三层循环枚举所有可能的 i、j、k逐一判断条件是否成立。复杂度 O(n^3)代码大概长这样def increasing_triplet(nums): n len(nums) for i in range(n): for j in range(i 1, n): for k in range(j 1, n): if nums[i] nums[j] nums[k]: return True return False这个写法是给新人做“语义确认”用的它能保证逻辑绝对正确但性能惨不忍睹。数组长度一旦到几千三层循环基本就卡死了。不过它有一个价值当你拿不准题目到底要什么时先写暴力版把答案验证一遍再去优化这样你能明确知道自己优化的目标是什么。2.2 动态规划正确但“杀鸡用牛刀”在暴力枚举的基础上稍微有经验的人会想到 LIS 的 DP 思路开一个dp数组dp[i]表示以nums[i]结尾的最长递增子序列长度。每到一个位置回头看前面所有比nums[i]小的位置取其中最大的dp[j]加一。如果某个dp[i]大于等于 3就说明存在长度为 3 的递增子序列。这个思路没错时间复杂度 O(n^2)空间复杂度 O(n)。对这道题来说属于性能还行但不够优雅的方案。面试里如果你只写这个版本面试官大概率会追问一句”能不能把空间和时间降下来”这里的瓶颈在于DP 需要依赖“当前位置之前所有值”的统计信息这导致它天然是 O(n^2) 的。而题目只需要长度 3完全可以把状态压缩掉。2.3 贪心哨兵法为什么两个变量就够了这里引入一个巧妙思维我们不关心完整的子序列长什么样只关心“当前前缀里有没有一个合适的 pair (第一小值, 第二小值)”。用两个哨兵变量first和second初始都设为无穷大。遍历数组时按顺序做两次比较规则如下如果nums[i]小于等于first就把first更新成nums[i]。否则继续判断nums[i]是否小于等于second如果是就更新second。如果nums[i]比second还大那说明当前元素能和前两棒组成三元组直接返回 true。为什么只靠两个变量就够用用一个生活化的类比解释你在排队找三个身高递增的人first就像你手里攥着的“最矮的替补”second则是“当前能找到的最优中间人”。每当你碰见一个更矮的人你会换掉first当你碰见一个比first高但又比second矮的你会换掉second一旦碰见比second还高的说明队列里已经攒够一组人可以收工了。3. 完整实现与关键细节3.1 标准代码C 与 Python 双版本先上结论这道题的标准解法空间复杂度 O(1)时间复杂度 O(n)。C 版本可以这样写bool increasingTriplet(vectorint nums) { int first INT_MAX, second INT_MAX; for (int num : nums) { if (num first) { first num; } else if (num second) { second num; } else { return true; } } return false; }Python 版本更简洁def increasing_triplet(nums): first second float(inf) for num in nums: if num first: first num elif num second: second num else: return True return False注意这里用的是而不是这是经过深思熟虑的。如果写成在遇到重复值时会出现问题。比如数组[1, 1, 1]如果用判断过程是这样的第一个 1 让first 1第二个 1 因为不小于first会走到elif又因为不小于second会更新second 1此时second first到了第三个 1它不小于second但first second已经不成立了所以严格递增条件被破坏。不过要是再遇到更大的值比如[1, 1, 2]用的写法会把第二个 1 更新成second然后第三个 2 大于second返回 true这明显是错的。所以用一方面保证first尽可能小另一方面避免把重复值误认为新的second一定要写成。3.2 手把手推一遍状态变化光看代码可能还觉得像玄学我用手动模拟的方式把全过程走一遍。假设数组是[2, 1, 5, 0, 3, 4]初始时first ∞second ∞步骤当前值操作firstsecond122 first更新 first2∞211 first更新 first1∞355 first5 second更新 second15400 first更新 first05533 first3 second更新 second03644 second发现三元组03第 6 步直接返回 true。这里有个一般人都会愣神的地方第 4 步时first被更新成 0但 0 的下标在 5 和 3 之后那三元组到底是 (1, 3, 4) 还是 (0, 3, 4)答案是无论哪个都成立。0 的下标虽然在 3 之前3 的下标是 40 的下标是 3所以按顺序看是 (0, 3, 4) 完全没问题。如果数组变成[5, 4, 6, 3, 7]手动模拟会发现 7 大于second6时返回 true此时三元组对应的是 (4, 6, 7) 而不是 (3, 6, 7)因为 3 排在 6 后面。算法本身并不需要输出具体是哪三个数它只需要确保“存在这样一组”所以这种更新方式不会破坏正确性。3.3 边界条件与初始化陷阱最容易让人纠结的边界情况是空数组、长度小于 3 的数组。这两种情况直接返回 false不需要额外代码也能天然做到因为循环跑完不会触发 return true。用INT_MAX还是用float(inf)都没问题但要注意如果数组里出现极大值且你初始化用INT_MAX在 C 里INT_MAX本身也是合法的数组值。不过这里用比较就算数组里真有INT_MAX也只是把first更新成INT_MAX不会误判。真正要小心的反而是另一种初始化方式把first初始化为nums[0]。这种写法会漏掉一种场景比如数组[3, 2, 1, 4]如果把first初始化为 3那么第 2 步遇到 2 时会把first更新为 2第 3 步遇到 1 时把first更新为 1第 4 步遇到 4 时因为4 second此时second仍然是INT_MAX所以会进入elif num second更新second 4最终返回 false。但实际数组[1, 2, 3]这样重新对齐后应该是存在的等等这里我故意举了个反例来说明问题nums [3, 2, 1, 4]中按顺序挑 (1, ?, 4) 需要第二个数在 1 后面且大于 1但 1 后面只有 4只有两个数所以确实不存在三元组返回值 false 正确。但如果数组是[3, 2, 1, 2.5, 3]初始化为nums[0] 3就麻烦了遍历到 1 时更新 first1遍历到 2.5 时因2.5 first且2.5 secondsecond 还是 3把 second 更新成 2.5遍历到 3 时因为3 second返回 true看着也正确。真正会出问题的是更刁钻的场景比如nums [5, 1, 5, 5, 2, 6]先看 5 初始化 first51 更新 first1第二个 5 时因为5 first且5 secondsecond 初始还是 5如果初始化 second 为 INT_MAX 就没事但如果你也手贱初始化为nums[0]那就废了。总之统一用无穷大初始化是零风险的选择别自己造轮子。4. 常见疑问与踩坑实录4.1 为什么先更新 first 再更新 second顺序能换吗很多人会把逻辑写成先判断num second再判断num first结果在某些测试用例上翻车。核心原因在于first和second之间存在一个隐形约束second必须是在first确定之后才可能被赋值也就是说second first这个关系必须始终成立。如果先判断second当num等于first时本来应该忽略这个值却可能因为num second把second更新成和first一样大的值两个哨兵相等后面的比较就全乱套了。举一个具体例子数组[1, 1, 2]如果先判断 second第一个 1second 还是无穷大1 second成立second 1first 保持无穷大。第二个 11 second成立second 1first 不动。第三个 22 second返回 true。但正确答案是什么是 false。这就是顺序颠倒导致的误判。这两个 if 的先后顺序不是编码风格问题而是正确性问题必须先用num first拦掉更小或相等的值才能保证second永远大于first。4.2 更新 first 会不会丢掉已经找到的三元组这是一个非常经典的心理障碍。比如你之前已经用first2, second5记录了“2 后面有个 5”结果后面出现一个 1你把first更新成 1那么记录(2, 5)的信息是不是丢失了再出现一个 6 时算法返回 true但这个 true 依赖的是(2, 5, 6)可你手上的first已经是 1 了这不就矛盾了吗答案是不矛盾因为second5在赋值时就隐式地携带了“当时那个 first”的信息。你不需要持续维护 first 和 second 的绑定关系只需要知道这个 second 曾经在某个 first 之后出现过。当出现 6 时算法并不需要用“当前 first”去组合而是用“历史上的某个 first”去组合。这个视角特别重要我在实际面试中问过不少人他们卡就卡在这一点上总觉得 first 更新会丢失信息。其实算法只负责回答“存不存在”不负责“是哪三个数”所以历史信息只要被 second 记住一次就永远不用回头。4.3 面试官最爱的追问方向这题在面试里考得不只是你能不能写出 O(n) 解法还会追问几个点。第一个追问能否输出具体是哪三个数。这时候需要额外引入一个数组记录每个数对应的“前驱下标”或者换一种思路先用两个数组分别记录每个位置左边的最小值和右边的最大值再遍历一遍找出符合条件的中间位置。这种解法其实是“三数组预扫描”思路虽然空间升到 O(n)但逻辑上更直观。第二个追问如果允许非严格递增允许相等代码怎么改。把两处改成就行了吗并不全对。因为非严格递增时重复值可以被连续使用比如[1, 1, 2]应该返回 true。如果把第一个 if 改成num first当num first时会走到elif又因为num second如果 second 之前没被赋值还是无穷大会赋值 second1反复处理会混乱。更稳妥的办法是维护一个count加滑动语义或者干脆把条件拆成if num first更新 firstelse if num first and num second更新 secondelse if num second返回 true。等于 first 的值直接跳过等于 second 的值也跳过这样才符合非严格递增的定义。第三个追问数组里有负数怎么办。负数和正数没有区别只要比较关系不变算法天然支持。真正要注意的是初始化值不能选成 0 这类可能被误判成“已经有一个哨兵”的值所以用无穷大才是正确的。5. 从一个题到一个方法今天算法笔记的延伸价值5.1 变体一二维矩阵里的增长路径有一种高频变体是把一维数组换成二维矩阵问能否找到一条从左上到右下、每一步只能向右或向下、且经过的值保持递增的路径。这类问题看起来很像动态规划但其实仍然是子序列思想的扩展维护“当前能到达的最小末尾值”。具体实现时用滚动数组记录走到当前位置的最小代价核心思维和first/second完全一致。如果你把这道题的贪心思想吃透再看这类变体就不会觉得陌生了。5.2 变体二任意长度 k 的递增子序列怎么判断当 k 变成很大时两个哨兵就不够用了需要把状态扩展成一个数组tails其中tails[i]表示长度为 i 的递增子序列的最小末尾值。这其实就是 LIS 问题的经典贪心加二分写法时间复杂度 O(n log n)。它的思想跟本题一脉相承每次用二分找到当前值能覆盖的位置更新那个位置的最小末尾值。如果某个位置超过了 k就说明能组成长度为 k 的递增子序列。所以这道“递增的三元子序列”其实是 k3 的特殊形态理解这一点你再看复杂版本时会有恍然大悟的感觉。5.3 一个值得养成的学习习惯每次刷完一道题不要急着跳到下一道花五分钟手动模拟一遍整个状态变化过程。这对理解贪心算法尤其有效。我第一次学这个题时就是拿笔在纸上画first和second的变化画完三个例子后才彻底说服自己“这算法不是碰巧正确”。你可以在草稿纸上任意写一个数组然后严格按代码逻辑走一遍观察first和second是不是始终满足first second为什么有时first突然变小但second不变这其实是给算法打一颗定心丸。这个习惯坚持一个月你会发现对很多中等难度的贪心题直觉会变得异常敏锐。这题还有一个特别适合动手验证的地方去 LeetCode 上用不同写法提交比如把改成看看有哪些测试用例会红。红过一次之后你对边界条件的记忆会比看十遍题解都深刻。我自己当年就是靠这种方式把“严格递增”和“非严格递增”的代码差异彻底刻在脑子里的。希望你今天学完这个算法也能顺手做一次“故意写错再观察报错”的练习这种从错误中反向学习的路径往往比一遍写对收获更多。