[leetcode]300-最长上升子序列

有空一起学习 2020年2月12日18:04:00 发表评论

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/longest-increasing-subsequence

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

  • 输入: [10,9,2,5,3,7,101,18]
  • 输出: 4
  • 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为O(n^2)。

进阶:你能将算法的时间复杂度降低到O(nlogn)吗?

二、题解

首先要搞清楚的是题意:求最长上升子序列。子序列不是子串,两者的区别是子序列可以不连续,子串必须连续

例如:[1, 3, 5, 2, 9],最长上升子序列是[1, 3, 5, 9],最长上升子串是[1, 3, 5]。

2.1 暴力法

题目的一个要求是用O(n^2)的时间复杂度来完成这个问题,如果有O(n^2)的时间复杂度,可以直接使用暴力破解的办法:

算法的时间复杂度和空间复杂度都是O(n^2)。

2.2 动态规划

dp[i]表示到第i个元素时的最大上升子序列长度,那么dp[i]就等于数组中上一个小于5的元素的最大上升子序列长度加1。

以[10,9,2,5,3,7]为例,i=5时如何求dp[i]?此时nums[i]=7,要想构造上升序列,它前面的数字都小于7才行。左边小于7的数字有三个:2、5和3。

  • 在数字1的地方,最大上升子序列的长度是1。
  • 在数字5的地方,最大上升子序列的长度是2;
  • 在数字3的地方,最大上升子序列的长度是2。

因为7大于三个数字,所以到达7的时候最大子序列长度肯定要加1,这个时候只有在上面三个数字中最大的上面加才能保证数字7的子序列最大。因此可以归纳出来的状态转移方程为:

$$dp[i]=max(dp[0], dp[1],..., dp[n]), n<i, nums[n]<=nums[i].$$\(\)

使用动态规划的时间复杂度也是O(n^2),空间复杂度O(n)。

2.3 二分法求解

二分法不容易想出来,即使是看题解也是看了几遍才明白。

考虑一个问题:假设存在数组tails,tails[i]表示最大上升子序列长度为i的子序列的末尾元素的最小值,这种情况下tails的长度就是最大子序列的长度了。存不存在这么一个数组呢,有没有办法构造出这样的一个数组?答案是肯定的。

以[10, 9, 2, 5, 7]为例解释tails数组每个元素的意义:

  1. 所有的数字都是长度为1的子序列,其中最小的数字是2,所以tails[1]=2。
  2. 长度为2的子序列有[2, 5], [2, 7]和[5, 7],其中末尾数最小的是5,所以tails[2]=5。
  3. 长度为3的子序列只有[2, 5, 7],末尾数只有一个就是7,所以tails[3]=7。

如果我们能构造出这个数组,那么问题就解决了。那么关键的问题是:如何知道遍历到哪个元素的时候,它的子序列长度是多少?

首先,暂且假设这个数组存在。结合tails数组的特性,可以确定的一个问题是tails[i]肯定大于tails[i-1],tails数组一定严格递增。因为题目求的是上升子序列,而tails数组保存的是每个子序列中的最小值,所以子序列右边的元素肯定大于左边的。

一个要注意的问题是tails[i]表示的是长度为i的子序列的末尾元素的最小值,以[1, 5, 3, 4]为例,最大上升子序列长度为2的有两个:[1, 5]和[1, 3],如果不取最小的末尾元素3,那么tails数组就是[1, 5],当遍历到4的时候,找到第一个大于它的数是5,此时下标等于2,也就是说最大上升子序列长度就是2。而实际上应该是3(子序列[1, 3, 4]),结果不对。

结合这个结论,在判断nums[i]的时候,只要从左到右找到第一个大于它的值的时候(使用二分法查找),这个下标就是它的最大子序列长度了。

这种情况下时间复杂度为O(nlogn)​,空间复杂度为O(n)。

三、代码

3.1 动态规划

3.2 二分法

通过二分法找到区间内第一个大于目标的元素:

求最长上升子序列:

[leetcode]300-最长上升子序列

本文共执行69次查询,耗时0.472秒!
有空一起学习

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: