LEETCODE 334. Increasing Triplet Subsequence 解题思路分析

题目大意:

递增的三元子序列

给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

  • 如果存在这样的 i, j, k,  且满足 0 ≤ i < j < k ≤ n-1,
  • 使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。

说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1) 。

示例 1:

输入: [1,2,3,4,5]
输出: true

示例 2:

输入: [5,4,3,2,1]
输出: false

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=334

解题思路分析:

本题求长度为3的递增子序列,我们使用2个变量代表,遍历到当前位置时的最小数m1,和次小数m2。初始时m1和m2均为整数最大值。如果当前数小于m1,m1更新为当前数,如果当前数大于等于m1并且小于m2,将m2更新为当前数,此时,说明我们找到了2个递增数字。如果当前数大于m2,说明我们找到了3个递增数,返回true即可。

我在网上看了大部分文章,基本讲到这里就结束了,但如果不能充分理解本解法的实质,你可能会对上述逻辑产生质疑,我们来用一个极端的例子说明。比如数组:

int[] nums =[11, 12, 0, 13];

根据上面的逻辑我们手动执行一遍代码:

  1. index为0,当前数字是11,最小值是11
  2. index为1,当前数字是12,次小值是12
  3. 重点来了!index为2,当前数是0,我们更新最小值为0,次小值不变。最多的疑问会出现在这里,当前最小值是0,次小值是12,然而在原数组中0是在12后面出现的,此时0和12虽然是递增,由于顺序原因,它并非是子序列,这样做合理吗?答案是肯定的,至少对于本题来说是合理的。因为将最小值从11变为0,并不能改变12是次小数的事实,只不过在12之前比12小的不是0,而是11。更新最小值的目的是为了之后有可能更改次小值做准备而已(比如这样的数组:[11,12,0,1,2])。本题这样做的原因是,题目只要求求出是否存在连续递增子序列,而没有要求列出具体的子序列内容,如果题目要求列出具体序列元素的话,这种解法显然行不通。
  4. index为3,当前数字为13,大于m2,返回true。

实现代码:

public boolean increasingTriplet(int[] nums) {
    int m1 = Integer.MAX_VALUE;
    int m2 = Integer.MAX_VALUE;
    for (int a : nums) {
        if (a <= m1) m1 = a;
        else if (a <= m2) m2 = a;
        else return true;
    }
    return false;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Increasing Triplet Subsequence.

Memory Usage: 43.3 MB, less than 6.98% of Java online submissions for Increasing Triplet Subsequence.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-334-increasing-triplet-subsequence-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。