您的位置首页 >要闻 > 人工智能 >

Rust 实现 LeetCode334 递增三元子序列,贪心思路完整题解

LeetCode334 这道递增三元子序列题,最优解法是贪心算法,只维护 first、second 两个变量,一次遍历数组就能完成判断,时间复杂度 O (n)、空间复杂度 O (1),用 Rust 写可以直接通过全部测试用例,能处理数组长度最大 5e5 的大数据场景,不会超时。题目的要求是找到下标 i

一、题目信息梳理

  • 题目:334. 递增的三元子序列(Increasing Triplet Subsequence)
  • 难度:中等
  • 输入:整数数组 nums,数组长度范围 1 ≤ nums.len () ≤ 5 * 10^5,元素范围 - 2^31 ~ 2^31-1
  • 输出:bool,存在严格递增三元子序列返回 true,否则 false
  • 示例
输入数组输出说明
[1,2,3,4,5]true存在大量递增三元组
[5,4,3,2,1]false整体递减,无法凑出
[2,1,5,0,4,6]true0,4,6 满足条件

二、贪心核心思路

  1. 初始化两个变量:first 记录遍历到的最小值,second 记录在 first 之后,比 first 大的最小候选值,初始都设为 i32 最大值。
  2. 逐个遍历数组里的每个数字 x:
  • 如果 x ≤ first:更新 first = x,把最小值压得更小,方便后续更容易找到更大的 second;
  • 如果 x > first 并且 x ≤ second:更新 second = x,缩小第二个候选值;
  • 如果 x > second:直接返回 true,代表找到了 first < second < x 的三元递增关系。
  1. 遍历全部元素后都没有触发上面条件,返回 false。

重点细节:就算 first 更新到 second 的后面也没关系,second 代表历史上已经存在过一个比它小的前置数字,不影响判断逻辑。

三、Rust 完整代码

pub fn increasing_triplet(nums: Vec) -> bool {

let mut first = i32::MAX;

let mut second = i32::MAX;

for &x in &nums {

if x <= first {

first = x;

} else if x <= second {

second = x;

} else {

return true;

}

}

false

}

四、代码测试调用示例

fn main() {

let case1 = vec![2,1,5,0,4,6];

println!("{}", increasing_triplet(case1)); // true

let case2 = vec![5,4,3,2,1];

println!("{}", increasing_triplet(case2)); // false

}

五、其他方案对比

  1. 暴力枚举:三层循环,O (n³),数组稍大直接超时,仅适合学习理解,不提交;
  2. 双向遍历:预处理每个位置左边最小值、右边最大值,O (n) 时间、O (n) 空间,适合新手理解,但不满足进阶 O (1) 空间要求;
  3. 贪心双变量(上面 Rust 方案):O (n) 时间、O (1) 空间,本题推荐标准写法。

六、踩坑点清单

  • 必须是严格递增,判断条件要用 <= 更新,不能用 <;
  • 初始值不能设置成 0,要使用 i32::MAX,兼容负数输入;
  • 子序列不需要连续,不要当成连续三数递增去处理;
  • 数组长度小于 3 的时候,天然不可能满足,直接返回 false,代码可以额外加判断优化。

【相关 FAQ】

问题 1:Rust 写 LeetCode334 递增三元子序列,贪心方案为什么 first 更新到 second 后面代码依然正确?

回答 1:Rust 实现 LeetCode334 递增三元子序列的贪心逻辑里,second 代表历史上已经存在一个比它小的前置数字,就算 first 被更新到 second 下标之后,只要后续出现大于 second 的数,就一定能找到一组合法的 i

问题 2:LeetCode334 递增三元子序列用 Rust 暴力写法为什么会超时?

回答 2:LeetCode334 递增三元子序列的数组上限是 5e5 个元素,暴力三重循环时间复杂度 O (n³),Rust 运行速度再快也扛不住大数据量,贪心写法 O (n) 遍历一遍才可以通过全部测试。

问题 3:Rust 写 LeetCode334 递增三元子序列,初始值为什么选 i32::MAX 而不是 0?

回答 3:LeetCode334 递增三元子序列的数组元素允许是负数,如果初始 first、second 设为 0,负数会直接跳过更新逻辑,产生错误结果,Rust 中使用 i32::MAX 才能覆盖全部合法输入范围。

问题 4:LeetCode334 递增三元子序列能不能用 Rust 的 LIS 最长递增子序列思路求解?

回答 4:可以,把 LeetCode334 递增三元子序列看成 LIS 问题,只要最长递增子序列长度≥3 就返回 true,Rust 也可以实现贪心 + 二分版本,但本题只需要判断长度为 3,双变量写法更简单高效。

【参考资料】

[2026-08-01](334. 递增的三元子序列题解)力扣 LeetCode

[2026-05-18](Increasing Triplet Subsequence greedy solution)CodeBricks

[2026-01-26](LeetCode334 Rust & algorithm analysis)ammarahmed.ca

[2022-01-11](334. 递增的三元子序列官方题解)力扣 LeetCode

【免责声明】

本文为 LeetCode334 递增三元子序列 Rust 算法题解整理,代码和思路仅供算法学习、刷题参考,提交前请自行在 LeetCode 平台验证;不同 Rust 版本、判题环境可能存在细微差异,不保证适配所有自定义场景。