题目地址(334. 递增的三元子序列)
给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列.
这道题是求解顺序数字是否有三个递增的排列, 注意这里没有要求连续的,因此诸如滑动窗口的思路是不可以的.
题目要求 O(n)的时间复杂度和 O(1)的空间复杂度,因此暴力的做法就不用考虑了.
我们的目标就是依次找到三个数字,其顺序是递增的.
因此我们的做法可以是从左到右依次遍历,然后维护三个变量,分别记录最小值,第二小值,第三小值.只要我们能够填满这三个变量就返回 true,否则返回 false.
维护两个变量,分别记录最小值,第二小值.只要我们能够填满这三个变量就返回 true,否则返回 false