LeetCode 334. 递增的三元子序列

Categories:

题目描述
思路分析
1. 解法一：贪心记录最小值（推荐）
相似题目

题目描述

✅ 334. 递增的三元子序列

思路分析

解法一：贪心记录最小值（推荐）

核心思路：

维护两个变量 first、second，分别表示目前最小和次小值。

遍历数组：

若 x <= first，更新 first；

否则若 x <= second，更新 second；

否则说明存在递增三元子序列。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

// 贪心维护最小和次小值
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;

        for (int x : nums) {
            if (x <= first) {
                first = x;
            } else if (x <= second) {
                second = x;
            } else {
                return true;
            }
        }

        return false;
    }
}

// 贪心维护最小和次小值
func increasingTriplet(nums []int) bool {
	first := int(^uint(0) >> 1)
	second := int(^uint(0) >> 1)

	for _, x := range nums {
		if x <= first {
			first = x
		} else if x <= second {
			second = x
		} else {
			return true
		}
	}

	return false
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	DP/贪心
376. 摆动序列	中等	贪心
392. 判断子序列	简单	双指针
674. 最长连续递增序列	简单	贪心
121. 买卖股票的最佳时机	简单	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/49983448