334. Increasing Triplet Subsequence

[songyy5517]

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.

Intuition This problem is to determine whether a triplet exists. One idea is based on Greedy Algorithm. Specifially, we loop through the whole array while keeping the first two smallest numbers [first, second] in the array. During the travarsing process, we update first and second constantly, if there exists an element greater than second, there exists a triplet.

[songyy5517]

Approach: Greedy Algorithm, always keep the first two smallest numbers

1. Exception handling;
2. Define variables first and second to store the first and the second number in the array, and second is behind first, and second > first;
   • first = num[0]; second = Integer.MAX_VALUE;
3. Loop through the array, for each number: （1）If cur_num > second, and second must be behind first , showing that there is a triplet [first, second, cur_num], and then return true; （2）If cur_num < first, update the variable first = cur_num ; （3）If cur_num > first (cur_num <= second), update the variable second = cur_num , because the triplets in [first, second', num] must be in [first, second, num] , if second' < second .
4. Returen false.

Complexity Analysis

• Time complexity: $O(N)$ , looping through the entire array costs the time of $O(N)$ ;
• Space complexity: $O(1)$ , additionally define constant-sized variables.

[songyy5517]

class Solution {
    public boolean increasingTriplet(int[] nums) {
        // 思路：贪心算法。遍历数组的同时，保存当前递增最小的两个数。
        // 1. 异常处理
        if (nums == null || nums.length == 0)
            return false;

        // 2. 定义变量
        // first: 递增序列的第一个数
        // second: 递增序列的第二个数，若存在于数组中，则之前一定有元素小于second。
        int first = nums[0], second = Integer.MAX_VALUE;

        // 3. 遍历数组
        for (int i = 0; i < nums.length; i++){
            // 当前数字大于second时，存在三元子序列
            if (nums[i] > second)
                return true;

            // 当前元素小于等于second，且小于等于first，则更新first，此时second还是没变
            else if (nums[i] <= first)
                first = nums[i];

            // 当前元素大于first，小于等于second，更新second
            else 
                second = nums[i];
        }

        return false;
    }
}

[songyy5517]

2024/5/9