题目地址：https://leetcode.com/problems/increasing-triplet-subsequence/description/
题目描述：
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Your algorithm should run in O(n) time complexity and O(1) space complexity.
Examples:
Given [1, 2, 3, 4, 5],
return true.
Given [5, 4, 3, 2, 1],
return false.
题目大意
判断一个无序的数组中是否包含长度为3的递增的序列。
解题方法
用LIS的解法一定能做出来的，但是不符合题目给出的O(n)的时间复杂度。看了别人的解法发现真的很巧妙。我们完全可以抛弃什么DP啊，dfs啊，老夫写代码就是一把梭，抓起键盘就是干！
既然要求我们从前到后遍历，那么在遍历的时候保存已经看到的最小值和次小值，然后再发现比这两个值大的的第3小的值存在的时候，那么就说明有长度为3的递增的子序列了。
当然，对于这种情况：
4 5 1 2 6
长度为3递增子序列有两种，但是由于我们保存的是最小的优先，所以最后的结果求得的是1 2 6这组。
整体的思想其实是很灵活的，保存的是遍历时见到的最小和次小，因此千万不要使用一成不变的min和max函数。
代码：
class Solution(object):
def increasingTriplet(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
first, second = float('inf'), float('inf')
for num in nums:
if num <= first:
first = num
elif num <= second:
second = num
else:
return True
return False
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发