LeetCode 솔루션 분류
[10/11] 334. Increasing Triplet Subsequence
본문
Medium
5672257Add to ListShareGiven an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.
Example 1:
Input: nums = [1,2,3,4,5] Output: true Explanation: Any triplet where i < j < k is valid.
Example 2:
Input: nums = [5,4,3,2,1] Output: false Explanation: No triplet exists.
Example 3:
Input: nums = [2,1,5,0,4,6] Output: true Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.
Constraints:
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1
Follow up: Could you implement a solution that runs in
O(n) time complexity and O(1) space complexity?Accepted
345,312
Submissions
811,181
태그
#Google
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 605 ms, faster than 90.03% of Python3 online submissions for Increasing Triplet Subsequence.
Memory Usage: 24.6 MB, less than 80.42% of Python3 online submissions for Increasing Triplet Subsequence.
Memory Usage: 24.6 MB, less than 80.42% of Python3 online submissions for Increasing Triplet Subsequence.
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
first_small = second_small = float('inf')
for num in nums:
if num <= first_small:
first_small = num
elif num <= second_small:
second_small = num
else:
return True
return False
