[LeetCode]300. 最长上升子序列(Longest Increasing Subsequence)

题目描述

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

示例:

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

说明:

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

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

解题思路

  1. 解法一:动态规划。dp 表示以当前数字结尾能够得到的最长上升子列,它取决于前面所有比它小的数字的结果。
  2. 贪心+二分。用一个一维数组 tail 表示长度为 i + 1 的上升子序列的末尾最小是几,遍历 nums 数组,不断的更新 tail 数组。具体见参考

代码

Python 2.7.12

解法一:动态规划

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = [1 for _ in range(len(nums))]
for idx, num in enumerate(nums):
for i in range(idx):
if nums[i] < num:
dp[idx] = max(dp[idx], dp[i] + 1)
return max(dp) if dp else 0

执行用时:964 ms
内存消耗:12.1 MB

解法二:贪心+二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
if length < 2:
return length

tail = [nums[0]]
for num in nums[1:]:
if num > tail[-1]:
tail.append(num)
continue
left, right = 0, len(tail) - 1
while left < right:
mid = (left + right) >> 1
if tail[mid] < num:
left = mid + 1
else:
right = mid
tail[left] = num
return len(tail)

执行用时 : 40 ms
内存消耗 : 12.1 MB

参考

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/