334. 递增的三元子序列
题目描述
输入一个整数数组 nums。判断能否从中挑出三个元素，它们的下标满足 i < j < k，数值满足 nums[i] < nums[j] < nums[k]。
也就是判断数组里是否存在长度为 3 的严格递增子序列。存在就返回 true，不存在返回 false。
示例 1
输入：nums = [1,2,3,4,5] 输出：true
解释：任取三个下标递增的元素都满足条件。
示例 2
输入：nums = [5,4,3,2,1] 输出：false
解释：数组严格递减，找不到这样的三个数。
示例 3
输入：nums = [2,1,5,0,4,6] 输出：true
解释：取下标 1,4,5，对应 1 < 4 < 6。
数据范围
1 <= nums.length <= 5 * 10^5-2^31 <= nums[i] <= 2^31 - 1
进阶：能否做到时间复杂度 O(n)、额外空间 O(1)？
解题思路：贪心（维护两个最小值）
维护两个值：first 是目前见过的最小值，second 是“前面有更小数的”最小次大值。遍历时贪心地让这两个值尽可能小：x ≤ first 就更新 first，否则 x ≤ second 就更新 second，否则 x 比两者都大，找到了三元组。
为什么正确
second 不是正无穷时，它前面一定有一个更小的数。first 更新到 second 后面也不影响这一点，因为旧的更小数仍在 second 前面。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
要用 <= 而不是 <：相等的数不能算严格递增。first 更新后不要重置 second。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
first = float('inf')
second = float('inf')
for x in nums:
if x <= first:
first = x
elif x <= second:
second = x
else:
return True
return Falseclass Solution {
public boolean increasingTriplet(int[] nums) {
long first = Long.MAX_VALUE;
long second = Long.MAX_VALUE;
for (int x : nums) {
if (x <= first) {
first = x;
} else if (x <= second) {
second = x;
} else {
return true;
}
}
return false;
}
}class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
long first = LONG_MAX;
long second = LONG_MAX;
for (int x : nums) {
if (x <= first) {
first = x;
} else if (x <= second) {
second = x;
} else {
return true;
}
}
return false;
}
};func increasingTriplet(nums []int) bool {
first := math.MaxInt64
second := math.MaxInt64
for _, x := range nums {
if x <= first {
first = x
} else if x <= second {
second = x
} else {
return true
}
}
return false
}var increasingTriplet = function(nums) {
let first = Infinity;
let second = Infinity;
for (const x of nums) {
if (x <= first) {
first = x;
} else if (x <= second) {
second = x;
} else {
return true;
}
}
return false;
};function increasingTriplet(nums: number[]): boolean {
let first = Infinity;
let second = Infinity;
for (const x of nums) {
if (x <= first) {
first = x;
} else if (x <= second) {
second = x;
} else {
return true;
}
}
return false;
}其他解法
前后缀数组枚举中间元素，用 O(n) 空间换来直观性；贪心只维护 first 和 second 两个变量，空间 O(1)。
解法 2：前缀最小 + 后缀最大 时间 O(n)，空间 O(n)
leftMin[i] 记录 nums[0..i] 的最小值，rightMax[i] 记录 nums[i..n-1] 的最大值。枚举中间元素 nums[i]，只要 leftMin[i-1] < nums[i] < rightMax[i+1]，就存在递增三元组。
思路直观，容易证明正确。需要两个长度为 n 的辅助数组，不满足进阶要求的 O(1) 空间。
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
n = len(nums)
if n < 3:
return False
left_min = [0] * n
left_min[0] = nums[0]
for i in range(1, n):
left_min[i] = min(left_min[i - 1], nums[i])
right_max = [0] * n
right_max[n - 1] = nums[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], nums[i])
for i in range(1, n - 1):
if left_min[i - 1] < nums[i] < right_max[i + 1]:
return True
return Falseclass Solution {
public boolean increasingTriplet(int[] nums) {
int n = nums.length;
if (n < 3) return false;
int[] leftMin = new int[n], rightMax = new int[n];
leftMin[0] = nums[0];
for (int i = 1; i < n; i++) leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
rightMax[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
for (int i = 1; i < n - 1; i++) {
if (leftMin[i - 1] < nums[i] && nums[i] < rightMax[i + 1]) return true;
}
return false;
}
}class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n = nums.size();
if (n < 3) return false;
vector<int> leftMin(n), rightMax(n);
leftMin[0] = nums[0];
for (int i = 1; i < n; i++) leftMin[i] = min(leftMin[i - 1], nums[i]);
rightMax[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) rightMax[i] = max(rightMax[i + 1], nums[i]);
for (int i = 1; i < n - 1; i++) {
if (leftMin[i - 1] < nums[i] && nums[i] < rightMax[i + 1]) return true;
}
return false;
}
};func increasingTriplet(nums []int) bool {
n := len(nums)
if n < 3 {
return false
}
leftMin := make([]int, n)
rightMax := make([]int, n)
leftMin[0] = nums[0]
for i := 1; i < n; i++ {
leftMin[i] = min(leftMin[i-1], nums[i])
}
rightMax[n-1] = nums[n-1]
for i := n - 2; i >= 0; i-- {
rightMax[i] = max(rightMax[i+1], nums[i])
}
for i := 1; i < n-1; i++ {
if leftMin[i-1] < nums[i] && nums[i] < rightMax[i+1] {
return true
}
}
return false
}var increasingTriplet = function(nums) {
const n = nums.length;
if (n < 3) return false;
const leftMin = new Array(n), rightMax = new Array(n);
leftMin[0] = nums[0];
for (let i = 1; i < n; i++) leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
rightMax[n - 1] = nums[n - 1];
for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
for (let i = 1; i < n - 1; i++) {
if (leftMin[i - 1] < nums[i] && nums[i] < rightMax[i + 1]) return true;
}
return false;
};function increasingTriplet(nums: number[]): boolean {
const n = nums.length;
if (n < 3) return false;
const leftMin = new Array<number>(n), rightMax = new Array<number>(n);
leftMin[0] = nums[0];
for (let i = 1; i < n; i++) leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
rightMax[n - 1] = nums[n - 1];
for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
for (let i = 1; i < n - 1; i++) {
if (leftMin[i - 1] < nums[i] && nums[i] < rightMax[i + 1]) return true;
}
return false;
}