class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
}
};
334. 递增的三元子序列
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5] 输出：true 解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1] 输出：false 解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6] 输出：true 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
提示：
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1
进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？
相似题目
原站题解
javascript 解法, 执行用时: 80 ms, 内存消耗: 58.5 MB, 提交时间: 2023-06-12 15:43:38
/**
* @param {number[]} nums
* @return {boolean}
*/
var increasingTriplet = function(nums) {
const n = nums.length;
if (n < 3) {
return false;
}
let first = nums[0], second = Number.MAX_VALUE;
for (let i = 1; i < n; i++) {
const num = nums[i];
if (num > second) {
return true;
} else if (num > first) {
second = num;
} else {
first = num;
}
}
return false;
};
golang 解法, 执行用时: 144 ms, 内存消耗: 22 MB, 提交时间: 2023-06-12 15:43:19
func increasingTriplet(nums []int) bool {
n := len(nums)
if n < 3 {
return false
}
first, second := nums[0], math.MaxInt32
for i := 1; i < n; i++ {
num := nums[i]
if num > second {
return true
} else if num > first {
second = num
} else {
first = num
}
}
return false
}
python3 解法, 执行用时: 116 ms, 内存消耗: 35.7 MB, 提交时间: 2023-06-12 15:43:06
# 贪心解法
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
n = len(nums)
if n < 3:
return False
first, second = nums[0], float('inf')
for i in range(1, n):
num = nums[i]
if num > second:
return True
if num > first:
second = num
else:
first = num
return False
java 解法, 执行用时: 2 ms, 内存消耗: 128.7 MB, 提交时间: 2023-06-12 15:42:46
class Solution {
public boolean increasingTriplet(int[] nums) {
int n = nums.length;
if (n < 3) {
return false;
}
int first = nums[0], second = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
int num = nums[i];
if (num > second) {
return true;
} else if (num > first) {
second = num;
} else {
first = num;
}
}
return false;
}
}
cpp 解法, 执行用时: 100 ms, 内存消耗: 109 MB, 提交时间: 2023-06-12 15:42:22
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int len = nums.size();
if (len < 3) return false;
int small = INT_MAX, mid = INT_MAX;
for (auto num : nums) {
if (num <= small) {
small = num;
} else if (num <= mid) {
mid = num;
}
else if (num > mid) {
return true;
}
}
return false;
}
};
python3 解法, 执行用时: 164 ms, 内存消耗: 35.6 MB, 提交时间: 2023-06-12 15:40:55
'''
建立一个初始化为3个无穷大子元素的数列，从左至右查看nums，逐个更新数列.
'''
from typing import List
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
ord = [inf] * 3
n = len(nums)
for i in range(n):
if nums[i] > ord[1]:
return True
elif nums[i] > ord[0] and nums[i] < ord[1]:
ord[1] = nums[i]
elif nums[i] < ord[0]:
ord[0] = nums[i]
return False