leetcode_递增的三元子序列

给定一个未排序的数组,请判断这个数组中是否存在长度为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.

致谢:

特别感谢@DjangoUnchained添加这道题并创建所有测试用例。

我的思路:设立两个变量one和two,one表示此元素之前的最小值,而two表示其前面有比他小的最小值,即arr【j】的最小值,这样只要有比two大的就存在arr[i] < arr[j] < arr[k] ,返回true;one的目的是为了更新two;如果一个值比one大,却又比two小,则跟新two;这样做是因为one是最小值,所以跟新的two也是满足情况的最小取值;

代码实现:

今天和喜欢的人一起打游戏,嘻嘻,开心

                                                                                     咯咯咯

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一...
    阿里高级软件架构师阅读 3,328评论 0 19
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,793评论 0 33
  • 第2章 基本语法 2.1 概述 基本句法和变量 语句 JavaScript程序的执行单位为行(line),也就是一...
    悟名先生阅读 4,271评论 0 13
  • 一、我们应该规划的是事件,而非时间。 大部分人在做时间管理时,都是从切割时间开始,按照一天的时间排的满满当当。规划...
    拾光流岁阅读 259评论 0 3
  • 坐于窗前,看白云曳尾飘过。一忽儿,如山峦拥簇、万峰覆雪,奔涌翻滚着仿似要漫到面前来。一忽儿,又如同庙会上的耍狮子,...
    莫小南阅读 559评论 5 11