递增三元子序列：O(1)空间解法是否有效？其原理是什么？

问题背景 #

题目要求：给定整数数组nums，判断是否存在下标i<j<k使得nums[i]<nums[j]<nums[k]，返回true或false；进阶要求实现O(n)时间、O(1)空间的解法。

我的困惑 #

我找到一种广为认可的高效解法：

var increasingTriplet = function (nums) {
    let a = Infinity, b = Infinity, c = Infinity;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] <= a) a = nums[i];
        else if (nums[i] <= b) b = nums[i];
        else if (nums[i] <= c) {
            return true;
        }        
    }
    return false;
}

这个解法能通过所有测试用例，但我对它的正确性存疑。比如输入数组[20, 100, 10, 12, 5, 13]，正确结果是true（比如三元组[10,12,13]符合要求），算法确实返回true，但此时a=5、b=12、c=13，这三个数在原数组中的下标并不满足i<j<k。

我猜这个算法只是验证存在性，不是找具体的三元组，但搞不懂它在这种场景下为什么能保证正确。另外，有没有办法做到既返回具体的合法三元组，又满足O(n)时间、O(1)空间的要求？

解法正确性说明 #

这个算法的核心不是要维护当前三个变量对应的下标顺序，而是通过维护两个尽可能小的递增数对(a,b)，确保只要出现比b大的数，就一定存在合法的三元组。

拆解一下逻辑：

• a始终是遍历到当前位置的最小数
• b始终是遍历到当前位置，比a大的最小数
• 当遇到一个数大于b时，不管此时的a是不是在b的后面，必然存在一个更早的数小于当前的b（因为b的定义就是在某个a之后出现的比a大的数），所以这个数、那个更早的a、b就构成了合法的三元组。

拿你举的例子[20, 100, 10, 12, 5, 13]一步步看：

1. 初始a=∞, b=∞
2. 20比a小，a更新为20
3. 100比a大、比b小，b更新为100
4. 10比a小，a更新为10（此时虽然a变了，但之前的20,100已经是一个递增对，现在换更小的a，更容易找到后续符合要求的b）
5. 12比a大、比b小，b更新为12（现在有了10,12这个递增对）
6. 5比a小，a更新为5（a再变小，但之前的10,12递增对依然存在）
7. 13比b大，直接返回true。此时当前a=5在b=12之后，但我们知道之前存在10（下标2）在12（下标3）之前，所以10,12,13就是合法的三元组。

算法的本质是不断优化a和b的取值（让它们尽可能小），最大化找到第三个数的概率，只要触发nums[i]>b，就一定存在至少一个合法三元组。

关于返回具体三元组的可能性 #

不存在满足O(n)时间、O(1)空间且能返回具体合法三元组的算法。原因很简单：

• O(1)空间意味着只能用常数个变量，没法记录所有可能的递增对的下标信息
• 更新a或b时会覆盖之前的记录，没法追溯到构成合法三元组的原始下标。比如上面的例子，a更新为5后，我们已经丢失了之前a=10的下标，没法通过当前的a和b直接找到对应的三元组。

如果一定要返回具体的三元组，至少需要O(n)空间，比如维护两个数组：

• leftMin：每个位置i记录nums[0..i]中最小值的下标
• rightMax：每个位置i记录nums[i..n-1]中最大值的下标
  然后遍历每个位置j，检查是否存在leftMin[j] < j且rightMax[j] > j，同时nums[leftMin[j]] < nums[j] < nums[rightMax[j]]，这种方法时间复杂度O(n)，但空间复杂度是O(n)。

内容的提问来源于stack exchange，提问作者kace91