LC334. 递增的三元组

题目描述

给你一个整数数组 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 进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

题目解析

题目在说什么

这道题其实很简单：给你一个数组，比如 [2,1,5,0,4,6]，你要判断里面有没有三个数，它们的位置是从左到右的（i < j < k），并且数字也是从小到大的（nums[i] < nums[j] < nums[k]）。有就返回 true，没有就返回 false。

注意：这三个数不需要连续，只要位置递增就行。比如 [1,2,3] 是递增三元组，[1,5,6] 也是（因为 1<5<6 且位置也是递增的）。

思路是怎么来的

想象你在玩一个游戏：你要从一堆数字里，按顺序挑出三个越来越大的数。你只能从左往右看，不能回头。

最笨的办法是：每看到一个数，就回头找前面有没有两个更小的数能组成递增三元组。但这样太慢了，数组可能很长（50万个数字），会超时。

那有没有更聪明的办法？我们换个角度想：我们不需要知道具体是哪三个数，只需要知道“有没有可能”。就像找对象，你不需要知道具体是谁，只需要知道“有没有机会”。

我们可以这样想：从左往右走，始终记住两个最小的递增数。比如：

• 第一个数（first）：到目前为止，你见过的最小的数。
• 第二个数（second）：到目前为止，你见过的一个比 first 大的数，而且这个 second 要尽量小。

为什么这样记？因为：

• 如果后面来了一个数比 second 还大，那 first < second < 这个数，就找到了递增三元组。
• 如果后面来的数比 first 还小，那就更新 first，让 first 变得更小，这样以后更容易找到比 first 大的 second。
• 如果后面的数在 first 和 second 之间，那就更新 second，让 second 变得更小，这样以后更容易找到比 second 大的第三个数。

这个思路就像你在爬山时，不断降低自己的“门槛”：你希望找到一个比前面两个都大的数，所以你就尽量让前面两个数变小，这样后面的数更容易比它们大。

代码逐步拆解

我们来看一个具体的例子：nums = [2,1,5,0,4,6]

第一步：初始化两个变量

int first = Integer.MAX_VALUE;  // 第一个数，初始为无穷大
int second = Integer.MAX_VALUE; // 第二个数，初始为无穷大

为什么设成无穷大？因为一开始我们还没见过任何数，所以先设成最大，后面遇到任何数都能更新它们。

第二步：遍历数组中的每个数（我们叫它 third）

for (int third : nums) {
    // 判断逻辑
}

第三步：逐个判断

我们一步步看：

• third = 2：2 <= first（因为 first 是无穷大），所以更新 first = 2。现在 first=2，second=无穷大。
• 为什么更新 first？因为 first 越小，以后越容易找到比 first 大的 second。

• third = 1：1 <= first（first=2），所以更新 first = 1。现在 first=1，second=无穷大。
• 注意：我们直接用更小的 1 替换了 first，这没问题，因为 first 只是记录“最小的数”，不关心位置。

• third = 5：5 > first（first=1），而且 5 <= second（second 还是无穷大），所以更新 second = 5。现在 first=1，second=5。
• 这一步很重要：我们找到了一个比 first 大的数 5，把它记作 second。现在 first < second。

• third = 0：0 <= first（first=1），所以更新 first = 0。现在 first=0，second=5。
• 注意：这里 first 变成了 0，比原来的 first 更小了。虽然 0 的位置比 second 的 5 靠后，但这没关系，因为我们只是记录“最小的数”，不关心位置顺序。实际上，这个 0 可能和后面的数组成新的递增三元组。

• third = 4：4 > first（first=0），而且 4 <= second（second=5），所以更新 second = 4。现在 first=0，second=4。
• 这一步很重要：我们把 second 从 5 降到了 4，这样以后更容易找到比 second 大的第三个数。

• third = 6：6 > second（second=4），所以返回 true。
• 找到了！因为 first=0 < second=4 < third=6，而且位置也是递增的（0 在 4 前面，4 在 6 前面）。

完整代码

class Solution {
    public boolean increasingTriplet(int[] nums) {