Hello everyone , I'm Qi Guanjie （qí guān jié ）, stay 【 Qi Guanjie 】 official account 、CSDN、GitHub、B Share some technical blog posts on the website and other platforms , It mainly includes front-end development 、python The backend development 、 Applet development 、 Data structure and algorithm 、docker、Linux Common operation and maintenance 、NLP And other related technical blog , Time flies , Future period , come on. ~
If you love bloggers, you can focus on the bloggers' official account. 【 Qi Guanjie 】(qí guān jié), The articles inside are more complete and updated faster . If you need to find a blogger, you can leave a message at the official account. , I will reply to the message as soon as possible .
This article was originally written as 【 Qi Guanjie 】（qí guān jié ）, Please support the original , Some platforms have been stealing blog articles maliciously ！！！ All articles please pay attention to WeChat official account 【 Qi Guanjie 】.
Give you an array of integers nums , Determine whether there is a length of 3 The increasing subsequence of .
If there is such a triple subscript (i, j, k) And meet i < j < k , bring nums[i] < nums[j] < nums[k] , return true ; otherwise , return false .
Example 1：
Input ：nums = [1,2,3,4,5]
Output ：true
explain ： whatever i < j < k All triples satisfy the meaning of the question
Example 2：
Input ：nums = [5,4,3,2,1]
Output ：false
explain ： There are no triples that satisfy the meaning of the question
Example 3：
Input ：nums = [2,1,5,0,4,6]
Output ：true
explain ： A triple (3, 4, 5) Satisfy the question , because nums[3] == 0 < nums[4] == 4 < nums[5] == 6
Tips ：
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1** Advanced ：** You can achieve a time complexity of O(n) , The space complexity is O(1) Is there a better solution ？
Refer to the solution of Miyoshi Sanye .f Maintain an ascending sequence with each number as small as possible , Here, because only the length is 3 Sequence , We simplify judgment , Maintenance only 2 Just one . Miyoshi Sanye's idea is very good in finding the longest ascending sequence .
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
n = len(nums)
f = [2**31-1,2**31-1] # Maintain an ascending sequence with each number as small as possible
for i in range(n):
t = nums[i]
if t > f[1]:
return True
elif f[0] < t < f[1]:
f[1] = t
elif f[0] > t:
f[0] = t
return False
