leetcode Increasing Triplet Subsequence

leetcode 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 < kn-1 else return false.Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

题目地址: leetcode Increasing Triplet Subsequence

题意:给定一个长度为n的乱序的数组arr,让你求是否有i,j,k三个数,使得 arr[i] < arr[j] < arr[k] ( 0 ≤ i < j < k ≤ n-1)

思路:

设 x1为到目前为止的最小值 ,  x2为到目前为止至少有一个数比x2小的最小的数。

初始时设置x1 = x2 = INT_MAX ,然后遍历数组,不断的更新x1和x2 具体如下

  • num <= x1,  此时将x1设置为num
  • 若 x1 < num <= x2,则 把x2 设置为num
  • x2 < num  说明有解,返回true即可

简单的说,上述的过程就是不断的缩小x1和x2,看看是否有第三个数 比x2大。

如果出现第三个数 num > x2,则之前必定还有个数x 小于x2,就是说满足 x < x2 < num,就是说有答案啦。

 

Python

C++ 

Java

 

 

 

本题是leetcode 334 Increasing Triplet Subsequence题解,

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Increasing Triplet Subsequence
本文地址:https://www.hrwhisper.me/leetcode-increasing-triplet-subsequence/

您的支持将鼓励我继续创作!

Leetcode , , , , . permalink.

3 thoughts on “leetcode Increasing Triplet Subsequence

  1. I am wrong, x2 代表了有一个数比当前这个数小,此时只要找到比这个数大的,就可以认为是正确答案了,我的想法就丢失了可能性,非常好的方法,谢谢

  2. 我觉得这个答案有问题,如果用例为[2,3,1,5],按照解法的策略更新时,会认为3(x2),1(x1),5是答案,是这样的吗?在x1变化时,x2应该重置为INT_MAX吧?

Leave a Reply

Your email address will not be published. Required fields are marked *