0334. Increasing Triplet Subsequence¶
题目信息¶
- 题号:
0334
- 难度:
Medium
- 主题:
数组、三元素子序列、严格递增、下标顺序
- 原题:
- 重点:
三个下标必须严格递增、三个数值也必须严格递增、元素不要求连续
题目重述¶
给定整数数组 nums,判断是否存在三个下标 i、j、k,满足 i < j < k 且 nums[i] < nums[j] < nums[k]。只要存在任意一组三元素严格递增子序列就返回 true,否则返回 false。
数组长度位于 [1, 5 * 10^5],元素位于 32 位有符号整数范围。三个元素在原数组中可以不连续,但不能改变出现顺序;相等值不能满足严格递增条件。进阶要求 O(n) 时间和 O(1) 额外空间。
自建示例¶
需要跳过中间元素:
输入:nums = [5, 1, 4, 2, 3]
输出:true
解释:下标 1、3、4 对应的数值 1、2、3 严格递增,虽然它们不是从数组开头连续取得。
只有相等值:
输入:nums = [3, 3, 3]
输出:false
解释:任意三个值都相等,不满足严格小于关系。
只保留最有希望的前两个数¶
扫描到当前位置时,维护一个最小的 first,以及在 first 之后出现、且尽可能小的 second。遇到 x:若 x <= first,用它替换 first;否则若 x <= second,用它替换 second;若 x 同时大于两者,就得到 first < second < x 的三元组。
替换不会破坏下标顺序:first 只来自当前或更早位置,second 只在当前值大于 first 时更新,因此保存的 first 必定位于 second 之前。用 <= 更新是为了让相等值不能错误地推进到更长的严格序列,同时给后续更大值留下最小前缀。
C++ 实现¶
class Solution {
public:
bool increasingTriplet(std::vector<int>& nums) {
int first = INT_MAX;
int second = INT_MAX;
for (int value : nums) {
if (value <= first) {
first = value;
} else if (value <= second) {
second = value;
} else {
return true;
}
}
return false;
}
};
代码分析¶
first 和 second 不是固定的某两个下标,而是到当前位置为止最有利于扩展的状态;较小的前缀不会减少后续可选值。两个变量始终保持严格候选关系,第三次进入 else 才返回真。算法只扫描一次数组,时间复杂度为 O(n),额外空间为 O(1)。