334.increasing-triplet-subsequence.md

题目地址(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。

关键点解析

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

代码

代码支持： JS, Python3

JS Code：

/*/** * @param {number[]} nums * @return {boolean} */varincreasingTriplet=function(nums){if(nums.length<3)returnfalse;letn1=Number.MAX_VALUE;letn2=Number.MAX_VALUE;for(leti=0;i<nums.length;i++){if(nums[i]<=n1){n1=nums[i];}elseif(nums[i]<=n2){n2=nums[i];}else{returntrue;}}returnfalse;};

Python3 Code:

classSolution: defincreasingTriplet(self, A: List[int]) ->bool: a1=a2=float("inf") forainA: ifa>a2: returnTrueelifa>a1: a2=aelse: a1=areturnFalse

复杂度分析

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

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