题目描述
思路解析
一句话答案：LeetCode 334 递增的三元子序列：贪心维护 first、second 两个尽量小的值，一旦冒出比 second 还大的数，递增三元组必成立，一遍扫定答案，时间 O(n)、空间 O(1)。
存在三个下标让数值一路递增吗
给一个整数数组 nums，问能不能找出三个下标 i＜j＜k，让 nums[i]＜nums[j]＜nums[k]，即挑出严格递增的三个数，能返 true、不能返 false。三个数不必挨在一起。题面 nums=[2,1,5,0,4,6] 返回 true，因 0、4、6 递增；nums=[5,4,3,2,1] 递减，凑不出两个递增，返回 false。
三层枚举 i、j、k 慢在哪
三个下标要凑成 i＜j＜k，一个写法是三层循环枚举 i、j、k，撞上 nums[i]＜nums[j]＜nums[k] 就返回 true。可数组有 n 个数，三层嵌套约 n³ 种搭配，n 到一千就十亿次比较，超时。只枚举中间的 j、往左找更小往右找更大，仍是 O(n²) 拖不动。
只记两个最小值，怎么就不漏
与其反复枚举，不如换一种贪心的记法——每个数只扫一遍、当场决定它更新谁：first 记「目前见过的最小值」、second 记「某个更小的数之后凑成递增二元组的第二个数」——二元组就是按前后顺序排好的一对递增数——两者都尽量往小压。遍历每个 x：x≤first 就把 first 换成更小的 x；否则 x≤second 就把 second 换成 x；再否则 x＞second，直接返回 true。
最反直觉的是：first 压小后，下标可能排到 second 后面，逻辑不就乱了？但并不会。second 被撑起来那一刻，就锁死一个事实——它左边出现过比它小的数。这是过去时，之后把 first 换更小只给第三个数留余地，动不了已成立的历史。所以只要冒出比 second 还大的 x，递增链「更小的 first ＜ second ＜ x」一定存在。
更新为什么用小于等于，哨兵怎么设
更新到底用 x≤first、x≤second 还是严格 ＜，直接决定成败：题目要严格递增，相等的值若用 ＜ 就不压小、会被当成能接续而误判，用 ≤ 才不会把重复值算成递增。初值则把 first、second 设成正无穷当哨兵——哨兵就是起手放的占位，设正无穷好让第一个数一定能压进来；Python 写 float('inf')，C++、Java 别用 INT_MAX、遇接近上限的大数会溢出，改 long。一旦 x＞second 返回 true，扫完没触发就 false。
跟着 [2,1,5,0,4,6] 走一遍
拿题面 nums=[2,1,5,0,4,6]，first、second 从正无穷起步。读 2→first=2；读 1→first=1；读 5→second=5（凑出 1＜5）；读 0→first=0（second 不动、1＜5 仍算数）；读 4→second=4（成 0＜4）；读 6＞second=4，返回 true——0、4、6 正是下标与值都递增的一组。
换成 nums=[5,4,3,2,1]，都更小，first→1，second 始终没被撑起来、一直是正无穷，等不到更大的数，返回 false。整趟扫一遍，时间 O(n)；只留两个变量，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
思路一句话：贪心维护 first=见过的最小值、second=次小值。冒出比 second 还大的数，三元组必真实存在。下面一步步演给你看。
例 1（存在） 开始。蓝色光标 cur 停在下标 0。first 先记成 ∞（还没见过最小值），second 也记 ∞。下面一个一个数往右扫，盯着 first / second 怎么被更新。
下标 0（值 9）不大于当前 first=∞，所以把 first 压小到 9——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 1（值 8）不大于当前 first=9，所以把 first 压小到 8——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 2（值 3）不大于当前 first=8，所以把 first 压小到 3——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 3（值 7）比 first=3 大、又不超过当前 second=∞，于是把 second 压小到 7。这意味着已经凑出一个递增二元组 3<7；只要之后再来个比 7 大的数，三元组就成了。
下标 4（值 2）不大于当前 first=3，所以把 first 压小到 2——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 5（值 6）比 first=2 大、又不超过当前 second=7，于是把 second 压小到 6。这意味着已经凑出一个递增二元组 2<6；只要之后再来个比 6 大的数，三元组就成了。
下标 6（值 1）不大于当前 first=2，所以把 first 压小到 1——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 7（值 5）比 first=1 大、又不超过当前 second=6，于是把 second 压小到 5。这意味着已经凑出一个递增二元组 1<5；只要之后再来个比 5 大的数，三元组就成了。
下标 8（值 0）不大于当前 first=1，所以把 first 压小到 0——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 9（值 4）比 first=0 大、又不超过当前 second=5，于是把 second 压小到 4。这意味着已经凑出一个递增二元组 0<4；只要之后再来个比 4 大的数，三元组就成了。
走到下标 10（值 12）：它比当前 second=4 还大。而 second 当初是被一个更小的 first=0 撑起来的——所以前面真有一个比 4 小的数。三个数 0 < 4 < 12 按顺序排好，递增三元组找到了，true！
例 1（存在） 扫完：高亮的三格正是一组合法的递增三元子序列（前后顺序对、值严格递增）。答案 true。
例 2（不存在） 开始。蓝色光标 cur 停在下标 0。first 先记成 ∞（还没见过最小值），second 也记 ∞。下面一个一个数往右扫，盯着 first / second 怎么被更新。
下标 0（值 7）不大于当前 first=∞，所以把 first 压小到 7——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 1（值 6）不大于当前 first=7，所以把 first 压小到 6——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 2（值 5）不大于当前 first=6，所以把 first 压小到 5——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 3（值 4）不大于当前 first=5，所以把 first 压小到 4——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 4（值 3）不大于当前 first=4，所以把 first 压小到 3——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 5（值 2）不大于当前 first=3，所以把 first 压小到 2——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
下标 6（值 1）不大于当前 first=2，所以把 first 压小到 1——起点越小，后面越容易接出更大的数。注意：压小 first 不会破坏已立起来的 second，因为 second 记的是「曾经存在过更小 first」这件事。
例 2（不存在） 扫完：数列一路递减，first 被一路压小、second 始终没被撑起来（一直是 ∞），自然不可能冒出比 second 大的数。挑不出递增的三个，答案 false。
边界先想清：长度<3 必然 false；严格递减或全相等都凑不出；只要扫描中出现「比 second 还大」即刻 true。
两个高频追问：压小 first 不破坏已成立的事实；推广到 k 元就是 LIS 的贪心+二分（tails 数组），k=3 即本题。
参考代码
def increasingTriplet(nums): first = second = float("inf") # 见过的最小、次小 for x in nums: if x <= first: first = x # 更小的起点 elif x <= second: second = x # 凑出递增二元组 else: return True # x>second 三元递增成立 return False复杂度
- 时间：O(n)，从左到右扫一遍，每个数只看一次
- 空间：O(1)，只用 first / second 两个变量
易错点
面试追问把动画讲成自己的话
追问把 first 压小到比 second 还靠后的位置，逻辑还对吗？
追问如果要找的是递增 k 元子序列（不止 3 个）怎么办？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
摆动序列
LeetCode 376 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题