334. Increasing Triplet Subsequence

[jason89521]

Practice Dates

• 2024/05/21

Description

Link: https://leetcode.com/problems/increasing-triplet-subsequence/description/

Solution

We first record two numbers, first and second, and then iterate over the nums vector. If the num is less than or equal to first, we reset first to it. If the num is greater than first but less than or equal to second, we reset second to it. When we find a number larger than both first and second, we know there is a triplet subsequence. This is because when second is set, it means we have found a number less than second. Consequently, when we find a number, called num, that is larger than second, we know there exists a triplet sequence: some number less than second -> second -> num.

impl Solution {
    pub fn increasing_triplet(nums: Vec<i32>) -> bool {
        let mut first = std::i32::MAX;
        let mut second = first;

        for &num in nums.iter() {
            if num <= first {
                first = num;
            } else if num <= second {
                second = num;
            } else {
                return true;
            }
        }

        false
    }
}

Performance

Time complexity: