viewv tech-blog
  • Jan 10, 2019
  • 0 views

Leetcode 300-Longest Increasing Subsequence 题解

 

Leetcode 300-Longest Increasing Subsequence 题解题目Given an unsorted array of integers, find the length of longest increasing subsequence.Example:Input: [10,9,2,5,3,7,101,18]Output: 4 Explanation: The...

Leetcode 300-Longest Increasing Subsequence 题解

题目

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

分析

采用动态规划的思想，这里是第一种方法\(O(n^2)\)的时间复杂度。

设置一个dp数组，这个数组dp[i]保存着到位置i的最长递增字符串，最后返回dp里面最长的就是答案，其中dp[i]表示以nums[i]为结尾的最长递增子串的长度，对于每一个nums[i]，我们从第一个数再搜索到i，如果发现某个数小于nums[i]，我们更新dp[i]，更新方法为dp[i] = max(dp[i], dp[j] + 1)，即比较当前dp[i]的值和那个小于num[i]的数的dp值加1的大小，我们就这样不断的更新dp数组，到最后dp数组中最大的值就是我们要返回的LIS的长度。

这里最有趣的是更新的时候，是dp[i]=max(dp[i],dp[j] + 1) 这个地方，看到dp[j] + 1的意思就是说i这个位置的值比j的值大，那么这里就可以使用dp[j]+1来更新dp[i]，这是重要的地方，选择这个和不选择这个的区别，是动态规划的常见问题，这里选择j就是要更新为dp[j]+1，不选择就还是dp[i]，取最大，便是需要更新的地方。

代码

下面是AC的代码：

class Solution:
​    def lengthOfLIS(self, nums):
​        length = len(nums)
​        dp = [1 for x in range(0, length)]
​        for x in range(0, length):
​            for y in range(0, x):
​                if nums[x] > nums[y]:
​                    dp[x] = max(dp[x], dp[y] + 1)
​            maxlength = max(maxlength, dp[x])
​        return maxlength

这个问题还有一个更快速的算法，能够优化时间到\(O(nlogn)\)的时间复杂度，使用二分查找的方法来优化。

优化-耐心排序

先建立一个空的dp数组，这个数组的意义是到i时对应长度的最长递增数组序列中的最大长度，下面是为什么这样设置的原因：

比如一个数组：

1,3,5,2,8,6

当我们循环到6时，我们一共有如下4种不同长度递增序列，这些序列保证这个递增序列在相同长度的序列中末尾数字是最小的：

1

1,2

1,3,4

1,3,5,6

这些序列都是未来有机会能够增长到最长的，如果此时我们循环到一个新的数字，插入时会有3种情况：

  • 新的数字小于所有序列的末尾数字，则说明长度为1的序列可以更新改变数字为新加入的这个数字。
  • 新的数字大于所有序列的末尾数字，则说明可以新建一个新的最长序列了，也就是在最后一个序列的基础上，增加这个新的数字，成为一个新的序列。
  • 新的数字位于中间位置，则将其补充到最大的小于它的序列上面去。

下面是例子：

插入9，最大位置：

1

1,2

1,3,4

1,3,5,6

1,3,5,6,9

再插入3，中间位置：

1

1,2

1,3,3

13,5,6

如果插入0，最末位置：

0

1,2

1,3,3

13,5,6

最大和最小都很好解决，但是中间位置的寻找，就需要用二分查找的操作来寻找。

下面是AC的代码：

class Solution:
​    def lengthOfLIS(self, nums):
​        dp = []
​        length = len(nums)
​        for i in range(0, length):
​            left = 0
​            right = len(dp)
​            while left < right:
​                mid = left + (right - left) // 2
​                if dp[mid] < nums[i]:
​                    left = mid + 1
​                else:
​                    right = mid
​            if right >= len(dp):
​                dp.append(nums[i])
​            else:
​                dp[right] = nums[i]
​        return len(dp)

感谢这篇博文，本文主要参考这篇博文，该博文中的代码写的很清晰。

Search