# 334. Increasing Triplet Subsequence

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
```

## Thoughts

给定数组中是否存在递增的三元组，要求O(N)时间O(1)空间。LIS的简化版，由于只要求找长度为3的子序列，tails数组长度为2，元素分别记录以长度为1和2的最小子序列尾，O(1)空间，且遍历tails只需要O(1)时间。

## Code

```python
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        tails = [math.inf] * 2
        for num in nums:
            if num <= tails[0]:
                tails[0] = num
            elif num <= tails[1]:
                tails[1] = num
            else: return True
        return False
        
```

```java
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int[] tails = new int[2];
        tails[0] = Integer.MAX_VALUE; tails[1] = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num <= tails[0]) {
                tails[0] = num;
            } else if (num <= tails[1]) {
                tails[1] = num;
            } else {
                return true;
            }
        }

        return false;
    }
}
```

## Analysis

时间复杂度O(N), 空间O(1).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/binarysearch/longest-increasing-subsequence/increasing-triplet-subsequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.