334. Increasing Triplet Subsequence

  • 38.4%

https://leetcode.com/problems/increasing-triplet-subsequence/#/description

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.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

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

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

java

1ms, 34.32%, 61/61, April.26th, 2016

https://leetcode.com/discuss/86891/concise-java-solution-with-comments

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public boolean increasingTriplet(int[] nums) {
int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
for(int n : nums){
if(n <= small) small = n;
else if(n <= big) big = n;
else return true;
}
return false;
}
}

cpp

8ms, 13.06%, 61/61, April.26th, 2016

https://leetcode.com/discuss/86593/clean-and-short-with-comments-c

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int c1 = INT_MAX, c2 = INT_MAX;
for(int x : nums){
if(x <= c1) c1 = x;
else if(x <= c2) c2 = x;
else return true;
}
return false;
}
};

python

52ms, 30.94%, 61/61, April.26th, 2016

https://leetcode.com/discuss/91827/python-easy-o-n-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def increasingTriplet(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
first = second = float('inf')
for n in nums:
if n <= first:
first = n
elif n <= second:
second = n
else:
return True
return False
谢谢你,可爱的朋友。