M-334. Increasing Triplet Subsequence

Loading...LeetCode

Loading...LeetCode

看下这个解一系列题目的思路!!!!!

Loading...LeetCode

pythonic的专业写法

pythonic的专业写法(用bisect, 本质上是维持一个排序好的长度至少为k-1 or k(取决于用try还是提前计算插入位置)(此题中k=3)的数组x, 接着遍历nums然后用binary search在x中找插入点), 并且维持数组x的长度不变, 如果插入点超过数组长度, 就是True, 如果遍历结束了还没有超过, 就是False.

一个有趣的python排序模块：bisect - 毛志谦 - 博客园

# 0 标答O(n), O(1)
# 思路是, 保留当前潜在的递增subSequence的最小的那个数x和中间小的那个数y, 并且往右遍历nums, 
# 如果碰到比x更小的数, 我们就准备更新潜在的subSequence, 更新的方法是, 先用更小的i来替换x, 如果
# 后面碰到了比i大, 比y小的数j, 我们就用j来更新y, 此时潜在的subSequence前两个数是i和j, 那么此时
# 如果后面碰到了比这俩都大的数, 说明存在这么一个递增的三位subSequence.
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        small = float('inf')
        big = float('inf')
        for i in nums:
            # 注意, 下面两个判断号是小于等于, 因为big只在i大于small的时候才big=i
            # 如果是小于, i=small的时候big会被更新为i, 此时不是递增的
            if i <= small:
                small = i
            elif i <= big:
                big = i
            else:
                return True
        return False