leetcode
leetcode 301 ~ 350
递增的三元子序列

递增的三元子序列

难度:

标签:

题目描述

给你一个整数数组 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,这是否意味着总是在找到第一个满足条件的三元组后停止搜索?如果数组中存在多个这样的三元组,会有什么不同的处理吗?
是的,该算法在找到第一个满足条件的三元组后会立即返回True并停止搜索。这是因为题目只需要判断是否至少存在一个递增的三元子序列,而不需要找出所有可能的三元组。如果数组中存在多个满足条件的三元组,该算法仍然在找到第一个后就停止处理,因此不会有不同的处理方式。
🦆
为什么在找到一个大于second_min_val的数字时可以确信存在一个递增的三元子序列?是否有可能second_min_val并未真正更新成递增序列中的第二个元素?
当找到一个大于second_min_val的数字时,可以确信存在一个递增的三元子序列,因为按照算法逻辑,second_min_val只会在之前找到一个更小的min_val之后才会被更新。这意味着已经存在至少两个数min_val和second_min_val,且min_val < second_min_val。因此,当找到第三个数大于second_min_val时,就确定了一个递增的三元子序列(min_val, second_min_val, num)。在这种逻辑下,second_min_val确实是递增序列中的第二个元素。
🦆
算法中使用了float('inf')来初始化min_val和second_min_val,这种方法在处理非常大或非常小的数值时是否仍然有效?
使用float('inf')进行初始化是为了确保任何数组中的第一个元素都能更新min_val,而第二个大于min_val的元素能更新second_min_val。在Python中,float('inf')表示一个比任何其他浮点数都大的值。因此,即使数组中包含非常大的数值,只要这些数值是有限的,算法仍然有效。对于非常小的数值,同样有效,因为无论数值多么小,都小于float('inf')。
🦆
如果输入数组nums为空或只有一个或两个元素,算法的输出是什么?这与算法的预期行为是否一致?
如果输入数组nums为空或只有一个或两个元素,算法会返回False。这是因为至少需要三个元素才能形成一个递增的三元子序列。算法在这种情况下返回False是与预期行为一致的,因为不存在足够的元素来形成所需的序列。

相关问题

最长递增子序列

给你一个整数数组 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)) 吗?