增加三元组子序列 - 这个解决方案真的有效吗？为什么？

Question

我一直在努力解决leetcode的

增加三元组子序列问题。

给定一串数字，必须找出其中是否有满足a<b<c

的子序列。

数字不必连续，但索引需要排序；也就是说，由于

[1,2,0,3]

 有效，因此 

[1,2,3]

 为 true，但 

[3,2,1]

 为 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]

。

我们的结果对于该输入应该是正确的，因为

[10 12 13]

 满足条件。

对于该测试，该算法确实返回 true，但如果我们在成功时记录 a、b 和 c 的值，它们是

{ a: 5, b: 12, c: 13 }

，这不是正确的解决方案，因为这三个数字在原始数组。

两种可能的情况之一正在发生：

算法
• 错误。
该算法仅
• 验证所需子集的存在，但它并没有真正找到它。

我怀疑是后者，因为我无法构建一个算法给出错误结果的测试用例。然而，

我无法理解为什么在我暴露的情况下它保证是正确的背后的直觉。我还想知道返回正确子集的算法是否可以在 O(n) 时间和 O(1) 空间中工作。

Answer 1

您找到的解决方案代码是正确的。其背后的直觉是，如果

b

 设置为输入数组中的某个值，那么您 

知道 之前有一个较小的值并被分配给 a

。

如果稍后

a

 获得较小的值，这不会改变当前 

b

 值仍然是之前发生的较小值的证明的事实 - 我们只是没有将其存储在 

a

 中不再了。

如果在该状态下我们发现一个大于

b

的值，我们就证明存在递增三元组。我们可能不再引用该三元组中的第一个值，但这并不重要。我们拥有该三元组中的第二个这一事实就足以作为证据。

Answer 2

注意：

b

的实际值保证在此“b”之前满足较小的值。 

a

的值可能会被后一个较小的值取代，但这一操作不会改变过去存在正确子序列

older_a, b

的事实