LeetCode 300 最长上升子序列

Ciel Yang 收录于类别练习 OJ解题报告

2020-03-14 2020-03-14 约 1065 字预计阅读 3 分钟

本题是一道考查动态规划和贪心的典型题目，而且也有助于体会二者的不同。同时，本题还涉及了二分查找的灵活应用。

题目描述

原题链接如下： LeetCode 300 最长上升子序列

题目大意

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

注意：
子序列元素可以并不紧邻
子序列必须单调递增（即不可有相等元素）

输入与输出

输入数据是一个整数数组，而且其长度和元素的取值范围均无特殊说明。

示例输入为：

1
[10, 9, 2, 5, 3, 7, 101, 18]

最长的上升子序列是 [2, 3(5), 7, 101(18)]，它的长度是 4。所以，相应输出为：

1
4

解题思路

本体有两种解法，分别是动态规划和贪心法。

动态规划

关键点在于构建方便解题的状态，用数组 dp 记录每个数组元素 nums[i] 对应的状态，每个 dp[i] 的状态是：nums[i] 对应的最长上升子序列长度，而且要求子序列必须以 nums[i] 为结尾。因为 nums[i] 的左边可能有多个上升序列，如果它比某个序列的末尾元素还要大，那么把 nums[i] 添加到那个序列中就可以得到一个新的更长的上升序列。这样，状态转移的递推式就很好求解：

1
2
list = nums[0 .. i - 1].filter { it < nums[i] }
dp[i] = list.max() + 1 (如果 list 为空，则 max() 值为 0)

因为，实际上遍历每个元素时，都要对它前面地元素进行遍历筛选，所以时间复杂度为 O(N^2)。

贪心法

贪心法的核心想法在于：不断从数组中依次取出元素，然后构造一个尽可能长的上升序列，那么就要求这个上升序列地上升速度尽可能“慢”，这样才可能尽量多地向结果序列中加入新元素。实际地操作如下：

如果数组的下一个元素大于序列末尾元素，那么加入到序列地末尾，序列变长
如果下一个元素不大于末尾元素，那么序列长度不变，且按元素是否在序列中分情况讨论：
- 如果不在序列中，则替换序列中比它大的最小元素
- 如果在序列中，则无需任何操作

这样，不断把序列的各个元素替换为更小的元素，那么数组后面的元素就能尽可能多地加入序列。

实际，决定每个元素如何加入结果序列时，要使用二分查找搜索插入位置，所以总的时间复杂度为 O(N * logN)。

代码展示

动态规划：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        val lengths = IntArray(nums.size)
        for (i in nums.indices) {
            var len = 1
            for (j in 0 until i) {
                if (nums[i] <= nums[j]) continue
                len = len.coerceAtLeast(lengths[j] + 1)
            }
            lengths[i] = len
        }
        return lengths.max() ?: 0
    }
}

贪心法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
import java.util.*

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        val lengths = IntArray(nums.size)
        var cnt = 0
        nums.forEach {
            var index = lengths.binarySearch(it, 0, cnt)
            if (index < 0) {
                index = -1 - index
                lengths[index] = it
                if (index == cnt) cnt++
            }
        }
        return cnt
    }
}

**注意：**Java 或者 Kotlin 库函数中数组的二分查找方法都可以在数组没有目标元素时返回它的应该插入的位置，即：
结果 i 小于 0 代表数组无目标元素，而且 -i - 1 就是目标应该插入的位置
插入操作是，把相应位置及其后方元素后移，然后新元素放入这个位置
本体中无需后移操作，直接进行替换即可

目录