美文网首页
17 - Medium - 递增的三元子序列

17 - Medium - 递增的三元子序列

作者: 1f872d1e3817 | 来源:发表于2018-04-24 10:38 被阅读0次

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

正式的数学表达如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1,
使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。
要求算法时间复杂度为O(n),空间复杂度为O(1) 。

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

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

思路是使用两个指针m1和m2,初始化为整型最大值,我们遍历数组,如果m1大于等于当前数字,

则将当前数字赋给m1;如果m1小于当前数字且m2大于等于当前数字,那么将当前数字赋给m2,

一旦m2被更新了,说明一定会有一个数小于m2,那么我们就成功的组成了一个长度为2的递增子序列,

所以我们一旦遍历到比m2还大的数,我们直接返回ture。如果我们遇到比m1小的数,还是要更新m1,

有可能的话也要更新m2为更小的值,毕竟m2的值越小,能组成长度为3的递增序列的可能性越大

class Solution:
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        m1 = float("inf")
        m2 = float("inf")
        #         float("inf"), float("-inf")  表示正负无穷
        for index, num in enumerate(nums):
            if(m1 >= num):
                m1 = num
            else: 
                if(m2 >= num):
                    m2 = num
                else:
                    return True
        return False

相关文章

  • 17 - Medium - 递增的三元子序列

    给定一个未排序的数组,请判断这个数组中是否存在长度为3的递增的子序列。 正式的数学表达如下: 如果存在这样的 i,...

  • LeetCode-334.-递增的三元子序列

    LeetCode-334.-递增的三元子序列 334. 递增的三元子序列[https://leetcode-cn....

  • 334. 递增的三元子序列

    334. 递增的三元子序列[https://leetcode-cn.com/problems/increasing...

  • 【leetcode】递增的三元子序列

    【leetcode】递增的三元子序列 题目: 给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列...

  • 334. 递增的三元子序列

    334. 递增的三元子序列 问题 给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。 数学表达...

  • LeetCodeDay40 —— 递增的三元子序列★★☆

    334. 递增的三元子序列 描述 给定一个未排序的数组,请判断这个数组中是否存在长度为3的递增的子序列。 示例 思...

  • 递增的三元子序列

    递增的三元子序列 给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。数学表达式如下: 如果存在...

  • LeetCode | 0491. Increasing Subs

    LeetCode 0491. Increasing Subsequences递增子序列【Medium】【Pytho...

  • 递增的三元子序列

    题目:递增的三元子序列 给定一个未排序的数组,请判断这个数组中是否存在长度为3的递增的子序列。 正式的数学表达如下...

  • 递增的三元子序列

    给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。 数学表达式如下: 如果存在这样的 i, j...

网友评论

      本文标题:17 - Medium - 递增的三元子序列

      本文链接:https://www.haomeiwen.com/subject/mjmllftx.html