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，如果存在一个索引三元组 (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 * 105
-231 <= nums[i] <= 231 - 1
后续问题：你能实现一个时间复杂度为 O(n)，空间复杂度为 O(1) 的解决方案吗？


class Solution {
    public boolean increasingTriplet(int[] nums) {
        int small = Integer.MAX_VALUE; // 初始化一个较小值变量，将其设置为整数最大值
        int middle = Integer.MAX_VALUE; // 初始化一个中间值变量，将其设置为整数最大值

        for (int num : nums) { // 遍历数组中的每个元素
            if (num <= small) { // 如果当前元素小于等于较小值
                small = num; // 更新较小值为当前元素值
            } else if (num <= middle) { // 如果当前元素大于较小值且小于等于中间值
                middle = num; // 更新中间值为当前元素值
            } else { // 如果当前元素大于中间值，说明找到了满足条件的三元组
                return true; // 返回 true
            }
        }

        return false; // 遍历完数组后，如果没有找到满足条件的三元组，返回 false
    }
}

这段代码定义了一个 increasingTriplet 函数，该函数接受一个整数数组 nums 作为参数。首先初始化两个变量 small 和 middle，分别表示较小值和中间值。遍历数组中的每个元素，如果找到一个元素大于中间值，说明存在满足条件的三元组。如果遍历完数组后仍未找到满足条件的三元组，则返回 false。这个解决方案的时间复杂度为 O(n)，空间复杂度为 O(1)。