LeetCode 334. 递增的三元子序列
目录
题目描述
题意分析
给定整数数组
nums，判断其中是否存在三个下标i < j < k，使得nums[i] < nums[j] < nums[k]。存在返回true，否则返回false。两个词要抠清楚。一是「子序列」而非「子数组」，三个下标只要求递增，不要求相邻，中间隔多远都可以。二是数值上要求严格递增，
nums[i] < nums[j]中的等号不成立，所以重复元素不能用来凑长度。最重要的约束信号是题目只问存在性，不要求返回具体是哪三个元素，也不要求统计有多少组。只需要一个布尔值，意味着我们可以在扫描过程中丢弃大量细节，只保留「离成功还差多远」这一点点状态。
数据范围是 $1 \le n \le 5 \times 10^5$，配合进阶要求「$O(n)$ 时间复杂度和 $O(1)$ 空间复杂度」，等于直接封死了 $O(n^2)$ 的动态规划和需要额外数组的做法：答案必须在一次遍历里给出，且只能用常数个变量。
边界情况包括：数组长度不足 3 时必然返回
false；全部元素相同时返回false；严格递减的数组返回false；元素取值可以到 $\pm(2^{31} - 1)$，所以选哨兵值时要小心。
解法：维护两个最小递增结尾
核心思路
题目只判断是否存在长度为
3的严格递增子序列，不需要还原下标。扫描时维护两个“门槛”：
first：当前前缀中最小的单个元素；second：当前前缀中所有递增二元组里，最小的结尾值。对当前数
num，若num <= first，就降低第一道门槛；否则若num <= second，说明存在更早的first < num，用它降低第二道门槛；否则已有某个递增二元组以second结尾，且second < num，三元组成立。贪心保留更小的结尾不会漏解：结尾越小，越容易被后面的数超过。两处分支都使用
<=，使相等元素只更新门槛而不会增加序列长度，从而维持“严格递增”。
first后来可能出现在second的右侧，但不影响正确性。second被设置时，历史上已经存在一个位于它左侧且更小的元素；后续降低first不会抹掉这个事实。例如[5,6,1,7]中最终门槛是first=1、second=6，合法三元组仍是5、6、7。
解题步骤
- 将
first、second初始化为正无穷。- 从左到右扫描数组。
num <= first时更新first。- 否则若
num <= second，更新second；此时一定存在更早的元素小于它。- 否则
num > second，直接返回true。- 扫描结束仍未找到第三个更大的数，返回
false。
代码实现
class Solution {
public boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int num : nums) {
if (num <= first) {
first = num;
} else if (num <= second) {
second = num;
} else {
return true;
}
}
return false;
}
}
func increasingTriplet(nums []int) bool {
maxInt := int(^uint(0) >> 1)
first, second := maxInt, maxInt
for _, num := range nums {
if num <= first {
first = num
} else if num <= second {
second = num
} else {
return true
}
}
return false
}
复杂度分析
- 时间复杂度：$O(n)$。数组只扫描一次，每个元素执行常数次比较。
- 空间复杂度：$O(1)$。只维护两个门槛变量。
关键点总结
second不是数组第二小值，而是所有合法递增二元组中的最小结尾。- 一旦出现
num > second，second背后的合法前驱保证三元组下标顺序正确。- 两处
<=用于吸收重复值，确保推进条件始终是严格递增。- 这是最长递增子序列“最小结尾”贪心在目标长度为
3时的常数空间特例。
易错点总结
- 使用
<而不是<=，会把[1,1,1]或[1,2,2]中的重复值误当作递增。- 将三个判断写成独立的
if，同一个元素可能同时更新两个门槛。- 把
second理解为当前first的固定搭档，并强行校验二者下标，会错判[5,6,1,7]。- 只检查连续三个元素，混淆了子序列与子数组。
- 用前后缀数组也能做到线性时间，但需要 $O(n)$ 空间，不满足进阶要求。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 128. 最长连续序列 | 中等 | 数值连续而非下标递增 |
| 300. 最长递增子序列 | 中等 | 贪心加二分求 LIS 长度 |
| 673. 最长递增子序列的个数 | 中等 | 在 LIS 基础上统计方案数 |
| 674. 最长连续递增序列 | 简单 | 下标连续的递增段长度 |