递增的三元子序列

挺有趣的一道题:

给定一个整数数组 nums,判断其中是否存在三元递增子序列。

三元递增子序列是指三个元素,它们的下标关系是 i < j < k,同时满足 nums[i] < nums[j] < nums[k]

-- leetcode 334. 递增的三元子序列

要求空间复杂度为 $O(1)$、时间复杂度为 $O(n)$。

最开始、我的第一想法是单调栈来做,但是空间复杂度不符合要求。

这实际是在找「长度为 3 的递增子序列」是否存在,和经典的 最长递增子序列 十分相似。

假设当前迭代的元素是 x,定义:

  • b 为已发现的长度为 2 的递增子序列的末尾元素的最小值。
  • c 为已发现的长度为 1 的递增子序列的末尾元素的最小值,也即 x 左边的最小值。

下图中,a, b 形成了长度为 2 的递增子序列,c 是已经发现的最小值。

首先,肯定有 b > c,因为 c 是已经发现的最小值, 必定有 c <= a < b

现在分情况讨论:

  1. 如果 x > b,那么已经发现三元递增序列 a < b < x,直接返回 true 即可。
  2. 否则,如果 b >= x > c,那么,至少发现了两元递增序列 c < x,那么需要更新 b = x
  3. 最后的情况是,x <= c 的时候,此时只需要更新最小值 c = x

最开始,设置 bc 都为 INT_MAX 即可。

代码实现如下:

bool increasingTriplet(vector<int>& nums) {
    int b = INT_MAX, c = INT_MAX;
    for (auto x : nums) {
        if (x > b)
            return true;
        else if (x > c) {  // x <= b && x > c
            b = x;
        } else {  // x <= c
            c = x;
        }
    }
    return false;
}

(完)


相关阅读:最长递增子序列(nlogn 二分法、DAG 模型 和 延伸问题)

本文原始链接地址: https://writings.sh/post/increasing-triplet-subsequence

王超 ·
微信扫码赞赏
评论 首页 | 归档 | 算法 | 订阅