334. Increasing Triplet Subsequence

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {boolean}
 */

本题要求我们在数组 nums 中找出三元组 (i, j, k) 使得 i < j < k 以及 nums[i] < nums[j] < nums[k]

如果有符合条件的三元组则返回 true，否则返回 false

解题思路

这题的核心思路是贪心思想：在遍历过程中随时记录第一小与第二小的数字，如果我们发现有比我们记录的两个数字大的数字，则返回 true

为什么这个思路可以呢？

我们用一个最小的例子来说明：假设我们现在遍历了 [2, 4] 两个元素

此时最小的数字是 2、第二小的数字是 4

后面的元素有三种可能：

1. 比 2 小
2. 在 2 与 4 中间
3. 比 4 大

不难看出只有第三种情况出现时，才能返回 true

当第一种情况发生时，我们的策略是：更新最小的数字为当前数字

当第二种情况发生时，我们的策略是：更新第二小的数字为当前数字

当我们用更小的数字替换原来记录的数字时，我们实际上是在维护更容易符合后面元素的递增二元组，因为更小的数字只会增加未来找到第三个数的可能性，而不会减少

Javascript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function(nums) {
    let first = Number.MAX_SAFE_INTEGER
    let second = Number.MAX_SAFE_INTEGER

    for(const num of nums) {
        if(num <= first) {
            first = num
        } else if(num <= second) {
            second = num
        } else {
            return true
        }
    }
    return false
};