longest increasing subsequence nlogn 算法

O(n^2)

算法逻辑:贪心 + 二分搜索

数据定义补充:
开一个栈,将a[0]入栈,每次取栈顶元素top和读到的元素ai做比较,如果a[i]> top 则将a[i]入栈;如果a[i]<= top则二分查找栈中的比a[i]大的第1个数,并用a[i]替换它。 最长序列长度即为栈的大小top。

这是很好理解的,对于x和y,如果x < y且stack[y] < stack[x],用stack[x]替换stack[y],此时的最长序列长度没有改变,但序列继续变长的''潜力''增大了。
举例:原序列为1,5,8,3,6,7
开始1,5,8相继入栈,此时读到3,用3替换5,得到1,3,8;
再读6,用6替换8,得到1,3,6;
再读7,得到最终栈为1,3,6,7。最长递增子序列为长度4。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,354评论 0 33
  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 14,693评论 0 89
  • 《ilua》速成开发手册3.0 官方用户交流:iApp开发交流(1) 239547050iApp开发交流(2) 1...
    叶染柒丶阅读 13,800评论 0 11
  • 课程介绍 先修课:概率统计,程序设计实习,集合论与图论 后续课:算法分析与设计,编译原理,操作系统,数据库概论,人...
    ShellyWhen阅读 6,921评论 0 3
  • 最近每日熬夜看书,凌晨一点过后,也有过一次出门看星星的经历。夜晚的一切是静谧的,与白天的喧杂截然不同。于是,喜欢上...
    安辛baby阅读 2,087评论 0 1