递增的三元子序列

力扣 334. 递增的三元子序列

题目说明

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

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

提示：

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

示例

示例 1:

1
2
3

输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意

示例 2:

1
2
3

输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

示例 3:

1
2
3

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

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，我们可以贪心使得 a 最小， b 尽可能小，然后找到 c 即可（当 a，b 不再更新时，说明三元组找到了），让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 贪心
     */
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE; 

        // 使用 <= 是因为避免 2, 2, 3 这种情况, 或者 1, 2, 2 的情况
        for (int num : nums) {
            // 使得 a 为最小元素
            if (num <= a) {
                a = num;
            }
            // 使得 b 尽可能小
            else if (num <= b) {
                b = num;
            }
            // 如果 a, b 不更新了, 说明遇到了三元组
            else {
                return true;
            }
        }

        return false;
    }
}