Ricky.L的随笔
0%

LeetCode.300.最长递增子序列（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.300.最长递增子序列（中等）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

题解

最值问题考虑动态规划，看能不能把大问题先拆分为子问题+有限步骤。

如果已知最长严格递增子序列，它是怎么得来的呢？上一步的最小操作是什么？

  • 如果前面没有递增子序列，当前字符作为新的递增子序列起点。
  • 如果前面有了递增子序列，当前字符比前面子序列最后一个数字大，可以形成新的递增子序列，长度加1。

前面的递增子序列可能有很多个，应该追加到哪个递增子序列的后面？
找长度最大的递增子序列。

数组前面的部分又是怎么找到最长递增子序列的？
还是一样的拆解，递归进行，这里划分出了子问题+有限步骤。

  • 子问题是最优的，经过有限步骤得出下一个问题的最优解，符合最优子结构。
  • 子问题的结果不受更大问题的影响，无后效性。
  • 计算长的子数组的最长递增子序列的长度，都要访问前面的递增子序列的长度，有重叠子问题。

符合使用动态规划所有条件。

状态转移方程
设dp[i]为以nums[i]结尾的最长递增子序列的长度。
遍历nums[0, i - 1]，寻找j（0 <= j <= i - 1）：

  • 对于所有满足nums[i] > nums[j]的j，找出最大dp[j]，dp[i] = 1 + 最大的dp[j]。
  • 如果nums[i]比nums[0, i - 1]都小，dp[i] = 1。

复杂度
时间复杂度$O(n^2)$：
计算所有dp[i]得遍历整个数组，需要$O(n)$；
计算每个dp[i]需要遍历[0, i - 1]，即$O(n)$。
双循环共执行1 + 2 + 3 + ... + n - 1 = (1 + n - 1) * (n - 1) / 2 = n(n - 1) / 2次。

空间复杂度$O(n)$：
dp数组占用线性空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        val n = nums.size
        val dp = IntArray(n) { 1 }
        var maxLen = 1
        for (i in 1 until n) {
            var preMaxLen = 0
            for (j in 0 until i) {
                if (nums[i] > nums[j]) {
                    preMaxLen = maxOf(preMaxLen, dp[j])
                }
            }
            dp[i] = 1 + preMaxLen
            maxLen = maxOf(maxLen, dp[i])
        }
        return maxLen
    }
}

时间优化

计算所有dp[i]的时间能不能优化？
计算所有dp[i]必须要遍历整个数组，无法优化。

计算每个dp[i]的时间能不能优化？
先看计算单个dp[i]的过程：
是要在已经发现的递增子序列中看nums[i]能接到哪些子序列后面，再在能接上去的这些子序列中找一个长度最大的。

直接找之前最长子序列的去接行不行？
行，如果能接上肯定最好。

如果接不上最长的，还有必要去接短的递增子序列吗？
有必要的，比如数组[1, 6, 7, 2, 3, 4]，有递增子序列是[1]、[1, 6]和[1, 6, 7]，2是接不到[1, 6, 7]后面的，但是可以接在[1]后面形成[1, 2]，最后遇到3和4，可以接在[1, 2]后面形成长度为4的递增子序列，比[1, 6, 7]还要长。

这里就引发一个问题，如果之前最长的子序列可能会有多个，应该去接哪个？
跟末尾元素最小的比较，是最快的；否则要是接不上，得比较多次。
比如上面长度为2的子序列有[1, 6]和[1, 2]，后面遇到3和4肯定直接跟2比较，比较次数是最少的。

所以如果当前数字接不到最长的，但是能接到短的子序列后面，如果当前数字比之前子序列末尾元素小，接上去对后面接更长的子序列是有意义的。

能否在查找方法上做优化？
一说到查找和比较，就能想到最优化的查找元素方法是二分查找，可以把时间复杂度降低到$O(log n)$。

二分查找是要求在有序数组里做查找比较的，那就把递增子序列的末尾数字从小到大排序。

我们想通过比较末尾元素，是想更新某个长度的递增子序列的末尾元素为更小的。

递增子序列末尾元素的大小顺序和子序列的长度有没有什么关联？

可以发现，如果相同长度的子序列只保留最小的末尾数字，那么长度大的子序列的末尾元素一定比长度小的子序列的末尾元素大。
因为只有新的数字比原来短的递增子序列的末尾元素大，才能形成长度更长的递增子序列；如果新的数字比原来短的递增子序列的末尾元素小，是无法形成长度更长的递增子序列的。

所以二分查找是可行的，可以保存每个长度的递增子序列的最小末尾数字形成数组，递增子序列长度作为数组索引，数组元素默认就是严格递增。

遇到新的数字用二分查找，就可以知道应该更新哪个长度的子序列的末尾元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        if (nums.size == 1) return 1
        val n = nums.size
        // dp[i]表示以长度为i + 1的所有上升子序列中结尾最小的数，0 <= i <= n - 1，n为数组长度
        // 由于上升子序列的长度可能是小于n的，所以这里创建动态列表来作为状态存储
        val dp = mutableListOf<Int>()
        dp.add(nums[0])
        for (i in 1 until n) {
            // 可以形成更长的子序列
            if (nums[i] > dp.last()) {
                dp.add(nums[i])
            } else { // 不能形成更长的子序列，但是要更新之前子序列末尾的元素为更小的，方便后续快速比较
                var left = 0
                var right = dp.size - 1
                while (left <= right) {
                    val mid = left + (right - left) / 2
                    when {
                        // 要找比子序列末尾元素大的位置，所以不会是mid本身，要mid + 1
                        dp[mid] < nums[i] -> left = mid + 1
                        // dp[mid] > nums[i]，dp严格递增，不存在dp[mid] == nums[i]
                        else -> right = mid - 1
                    }
                }
                // 熟悉二分法可知，循环结束后，一定会有 nums[left - 1] < nums[i] < nums[left]
                // 更新子序列末尾元素为更小的
                dp[left] = nums[i]
            }
        }

        return dp.size
    }
}