题目链接
递增的三元子序列文章来源：https://www.toymoban.com/news/detail-817079.html
题目描述
文章来源地址https://www.toymoban.com/news/detail-817079.html
注意点
- 1 <= nums.length <= 500000
- 子序列的三个元素在原数组中可以不是连续的
- 实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案
解答思路
- 使用贪心算法，在遍历数组时，要记录当前数组中的最小值minVal （方便找第二小的值）以及递增二元组中的较大值tupleMaxVal （方便找递增三元子序列）。如果当前值大于tupleMaxVal，说明找到了递增三元子序列；如果当前值大于minVal 小于tupleMaxVal，说明找到了更小的递增二元组，需要更新tupleMaxVal ；如果小于minVal，则需要更新minVal，后续更新tupleMaxVal时只需要与minVal进行比较即可
代码
class Solution {
public boolean increasingTriplet(int[] nums) {
// 当前数组内的最小值
int minVal = Integer.MAX_VALUE;
// 递增二元组的较大值
int tupleMaxVal = Integer.MAX_VALUE;
for (int num : nums) {
// 找到递增三元组
if (num > tupleMaxVal) {
return true;
}
// 找到更小的递增二元组
if (num > minVal && num < tupleMaxVal) {
tupleMaxVal = num;
}
// 找到子数组最小值
if (num < minVal) {
minVal = num;
}
}
return false;
}
}
关键点
- 贪心算法的思想
- 更新当前数组的最小值和递增二元组的较大值
到了这里，关于递增的三元子序列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
