334. 递增的三元子序列

🟠   🔖  贪心 数组  🔗 力扣 LeetCode

题目

Given an integer array nums, return true if there exists a triple of indices(i, j, k)such thati < j < k andnums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Example 1:

Input: nums = [1,2,3,4,5]

Output: true

Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5,4,3,2,1]

Output: false

Explanation: No triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]

Output: true

Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Constraints:

• 1 <= nums.length <= 5 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

题目大意

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：

输入： nums = [1,2,3,4,5]

输出： true

解释： 任何 i < j < k 的三元组都满足题意

示例 2：

输入： nums = [5,4,3,2,1]

输出： false

解释： 不存在满足题意的三元组

示例 3：

输入： nums = [2,1,5,0,4,6]

输出： true

解释： 三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

• 1 <= nums.length <= 5 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

进阶： 你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

解题思路

1. 使用两个变量：

   • 维护两个变量 first 和 second，分别用于存储当前找到的最小和次小的数字。这两个变量用于跟踪潜在的递增三元组。

2. 遍历数组：

   • 遍历 nums 数组，对于每个元素：
     • 如果当前元素小于或等于 first，更新 first 为当前元素。
     • 如果当前元素大于 first 且小于或等于 second，更新 second 为当前元素。
     • 如果当前元素大于 second，则找到了一个递增的三元组（first < second < nums[i]），返回 true。

3. 返回结果：

   • 如果遍历完数组后没有找到满足条件的三元组，返回 false。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 数组的长度，只需遍历一次数组。
• 空间复杂度：O(1)，只使用常量空间来存储状态。

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function (nums) {
	let first = Infinity,
		second = Infinity;
	for (let num of nums) {
		if (num <= first) {
			first = num; // 更新最小值
		} else if (num <= second) {
			second = num; // 更新次小值
		} else {
			return true; // 找到一个递增三元组
		}
	}
	return false; // 未找到
};

相关题目

题号	标题	题解	标签	难度
300	最长递增子序列	[✓]	数组 二分查找 动态规划
1995	统计特殊四元组		数组 哈希表 枚举
2179	统计数组中好三元组数目		树状数组 线段树 数组 4+
2552	统计上升四元组		树状数组 数组 动态规划 2+