递增的三元子序列
难度:
标签:
题目描述
给你一个整数数组 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)
的解决方案吗?
代码结果
运行时间: 41 ms, 内存: 34.9 MB
/*
* 题目思路:
* 使用Java Stream API来处理这个问题虽然可以实现,但可能不会直接提高性能,因为Stream的本质还是基于迭代。
* 主要思路依然是遍历数组,维护两个变量来记录当前的最小值和次小值。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length < 3) {
return false;
}
int[] first = {Integer.MAX_VALUE};
int[] second = {Integer.MAX_VALUE};
return IntStream.of(nums).anyMatch(num -> {
if (num <= first[0]) {
first[0] = num;
return false;
} else if (num <= second[0]) {
second[0] = num;
return false;
} else {
return true;
}
});
}
}
解释
方法:
该题解使用了贪心算法的思路。我们维护两个变量min_val和second_min_val,分别表示遍历过程中的最小值和第二小值。遍历数组,如果当前元素小于等于min_val,则更新min_val;如果当前元素大于min_val但小于等于second_min_val,则更新second_min_val;如果当前元素大于second_min_val,说明找到了一个递增的三元组,返回True。如果遍历完数组没有找到递增的三元组,返回False。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在你的算法中,当遇到一个数字大于second_min_val时直接返回True,这是否意味着总是在找到第一个满足条件的三元组后停止搜索?如果数组中存在多个这样的三元组,会有什么不同的处理吗?
▷🦆
为什么在找到一个大于second_min_val的数字时可以确信存在一个递增的三元子序列?是否有可能second_min_val并未真正更新成递增序列中的第二个元素?
▷🦆
算法中使用了float('inf')来初始化min_val和second_min_val,这种方法在处理非常大或非常小的数值时是否仍然有效?
▷🦆
如果输入数组nums为空或只有一个或两个元素,算法的输出是什么?这与算法的预期行为是否一致?
▷相关问题
最长递增子序列
给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3] 输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7] 输出:1
提示:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶:
- 你能将算法的时间复杂度降低到
O(n log(n))
吗?