LeetCode Top Interview Questions 334. Increasing Triplet Subsequence (Java版; Medium)

系统管理员 2023-07-02 10:29 48阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 334. Increasing Triplet Subsequence (Java版; Medium) ##

#### 题目描述 ####

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
    
    Formally the function should:
    
    Return true if there exists i, j, k 
    such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
    Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
    
    Example 1:
    
    Input: [1,2,3,4,5]
    Output: true
    Example 2:
    
    Input: [5,4,3,2,1]
    Output: false

#### 第一次做; 参考题解, 核心: 找到最小的, 次小的, 次次小的 ####

//找到最小的, 次小的, 次次小的
    class Solution { 
        public boolean increasingTriplet(int[] nums) { 
            int small=Integer.MAX_VALUE, medium=Integer.MAX_VALUE;
            for(int i=0; i<nums.length; i++){ 
                int cur = nums[i];
                // cur <= small
                if(cur <= small)
                    small = cur;
                // small < cur <= medium
                else if(cur<=medium)
                    medium = cur;
                // cur > medium
                else 
                    return true;
            }
            return false;
        }
    }

#### [优秀解释][Link 1] ####

![format_png][]

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode.com/problems/increasing-triplet-subsequence/discuss/79004/Concise-Java-solution-with-comments.
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS8yOGE0OGE3NTE3ODJhOTRiMTQzYjUxNGI2MmQ4MjMzNC94bWxub3RlL0Q4RTQ3NTk4MTNGQzRGMTlCMkNEQjdBMDFCNUMyOTg2LzU2MzAx?x-oss-process=image/format,png