Sui Xin's Blog

[LeetCode]300. 最长上升子序列（Longest Increasing Subsequence）

Posted on In Disqus:

题目描述

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

示例:

输入: [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/

Related Posts