# 0334. 递增的三元子序列

### 题目地址(334. 递增的三元子序列)

<https://leetcode-cn.com/problems/increasing-triplet-subsequence/>

### 题目描述

```
给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k,  且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 1:

输入: [1,2,3,4,5]
输出: true
示例 2:

输入: [5,4,3,2,1]
输出: false

```

### 前置知识

* 双指针

### 公司

* 百度
* 字节

### 思路

这道题是求解顺序数字是否有三个递增的排列， 注意这里没有要求连续的，因此诸如滑动窗口的思路是不可以的。

题目要求 O(n)的时间复杂度和 O(1)的空间复杂度，因此暴力的做法就不用考虑了。

我们的目标就是`依次`找到三个数字，其顺序是递增的。

因此我们的做法可以是从左到右依次遍历，然后维护三个变量，分别记录最小值，第二小值，第三小值。只要我们能够填满这三个变量就返回 true，否则返回 false。

![334.increasing-triplet-subsequence](https://p.ipic.vip/swvj6t.jpg)

### 关键点解析

* 维护两个变量，分别记录最小值，第二小值。只要我们能够填满这三个变量就返回 true，否则返回 false

### 代码

代码支持： JS, Python3

JS Code：

```js
/*
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function (nums) {
  if (nums.length < 3) return false;
  let n1 = Number.MAX_VALUE;
  let n2 = Number.MAX_VALUE;

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] <= n1) {
      n1 = nums[i];
    } else if (nums[i] <= n2) {
      n2 = nums[i];
    } else {
      return true;
    }
  }

  return false;
};
```

Python3 Code:

```py
class Solution:
    def increasingTriplet(self, A: List[int]) -> bool:
        a1 = a2 = float("inf")

        for a in A:
            if a > a2:
                return True
            elif a > a1:
                a2 = a
            else:
                a1 = a
        return False
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/eyot5z.jpg)


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/334.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.