一、题目描述
给你一个整数数组 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 * 10^5-2^31 <= nums[i] <= 2^31 - 1
二、解题思路
为了解决这个问题，我们可以使用贪心算法来寻找递增的三元子序列。我们维护两个变量，分别代表目前找到的第一个最小值和第二个最小值。遍历数组时，我们按照以下步骤进行：
- 初始化两个变量
first和second为无穷大（可以使用整型的最大值）。 - 遍历数组中的每个元素
num：- 如果
num小于或等于first，则更新first为num。 - 否则，如果
num小于或等于second，则更新second为num。 - 否则，如果
num大于second，说明找到了一个递增的三元子序列，返回true。
- 如果
- 如果遍历完数组后没有找到递增的三元子序列，返回
false。
三、具体代码
class Solution {public boolean increasingTriplet(int[] nums) {// 初始化两个变量为整型的最大值int first = Integer.MAX_VALUE;int second = Integer.MAX_VALUE;// 遍历数组中的每个元素for (int num : nums) {// 如果当前元素小于或等于第一个最小值，则更新第一个最小值if (num <= first) {first = num;}// 否则，如果当前元素小于或等于第二个最小值，则更新第二个最小值else if (num <= second) {second = num;}// 否则，找到了递增的三元子序列，返回trueelse {return true;}}// 如果遍历完数组后没有找到递增的三元子序列，返回falsereturn false;}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 遍历数组：代码中有一个
for循环，该循环遍历数组nums中的每个元素。假设数组nums的长度为n，则循环将执行n次。 - 在循环内部，只有简单的比较和赋值操作，这些操作的时间复杂度为 O(1)。
因此，整个 increasingTriplet 方法的时间复杂度为 O(n)，其中 n 是数组 nums 的长度。
2. 空间复杂度
- 常量空间：代码中使用了两个整型变量
first和second，这两个变量在整个方法执行过程中始终保持不变的大小，不随输入数组nums的大小而改变。 - 输入空间：输入数组
nums本身不计入额外空间复杂度。
因此，整个 increasingTriplet 方法的空间复杂度为 O(1)，表示使用了固定数量的额外空间。
五、总结知识点
-
类定义：
class Solution：定义了一个名为Solution的类。
-
方法定义：
public boolean increasingTriplet(int[] nums)：定义了一个公共方法increasingTriplet，它接受一个整数数组nums作为参数，并返回一个布尔值。
-
整型变量初始化：
int first = Integer.MAX_VALUE;：使用Integer.MAX_VALUE初始化first变量，表示该变量被设置为整型的最大可能值。
-
增强型
for循环：for (int num : nums)：使用增强型for循环遍历数组nums中的每个元素。
-
条件判断：
if (num <= first)：条件判断语句，用于检查当前元素是否小于或等于first变量。else if (num <= second)：另一个条件判断语句，用于检查当前元素是否小于或等于second变量。
-
变量赋值：
first = num;和second = num;：将当前元素赋值给first或second变量。
-
逻辑返回：
return true;和return false;：根据条件判断的结果返回布尔值true或false。
-
贪心算法：
- 整个方法体现了贪心算法的思想，通过维护两个变量来寻找递增的三元子序列，而不是回溯所有可能的组合。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
