[LeetCode] 334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[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 * 105
-231 <= nums[i] <= 231 - 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 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/increasing-triplet-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是我们把遍历过程中遇到的可能组成上升子序列的三个数字分别记为 first, second 和 third，并把 first 和 second 设为 Integer.MAX_VALUE。开始遍历 input 数组，按照判断条件，我们会先遇到 first，然后如果有另一个数字大于 first 的话，就把他记为 second，如果再有一个数字大于 second 的话，则我们找到一个合法的解了。但是还有一种情况是如果我们找到 second 之后再遇到一个数字能小于 first 的话，我们就更新 first。这里的逻辑是尽量让 first 和 second 变得更小，这样能给第三个数字留充足的空间。

这里如果我们能找到一个数字比 first 更小的话（记为first*），此时三元组也是合法的。虽然 first* 出现在second 之后，但是他的出现并没有影响 second 的值，所以只要我们能找到一个数字大于 second 的话，那么还是能找到合法的解。

注意这道题是属于 LIS 最长上升子序列的题，只不过这个子序列的长度是固定的。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
	public boolean increasingTriplet(int[] nums) {
		int first = Integer.MAX_VALUE;
		int second = Integer.MAX_VALUE;
		for (int num : nums) {
			if (num <= first) {
				first = num;
			} else if (num <= second) {
				second = num;
			} else {
				return true;
			}
		}
		return false;
	}
}

JavaScript实现

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function (nums) {
	let first = Number.MAX_VALUE;
	let second = Number.MAX_VALUE;
	for (num of nums) {
		if (num <= first) {
			first = num;
		} else if (num <= second) {
			second = num;
		} else {
			return true;
		}
	}
	return false;
};