题目
- 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
- 1 <= nums.length <= 2500
- -104 <= nums[i] <= 104
进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
解题思路
递归暴力
这个一开始的思路是动态规划，但是动态规划的实现比较复杂，所以先用递归暴力的方法来实现。每一个单个的数字都可以作为一个递增子序列，把整个序列分为该以单个数字形成的子序列 a 和剩下数字组成的子序列 b 两部分。编写一个递归函数来计算 a 和 b 能够组成的最长递增子序列的长度。每次递归都要判断 b序列的开头数字是否大于 a 的最后一个数字，如果大于，则需要比较比较加入 b 的开头数字和 a 的最后一个数字组成的子序列的长度和不加入 b 的开头数字组成的子序列的长度，取最大值。否则就直接计算去掉 b 的开头数字后的子序列与 a 能够组成的最长递增子序列的长度。
1 | func max(num1, num2 int) int { |
然后不出意外的超时了，时间复杂度是 O(n^2)，以下面的代码为例：
1 | func main() { |
而这其实可以考虑增加一些限制条件，当已经计算出的最大长度的子序列长度超过了剩下子串的长度时，就可以直接返回了。
1 | func lengthOfLIS(nums []int) int { |
还有当 b0 子串的第一个元素比 a0 子串的最后一个元素大时，b 去掉该元素变为 b1，而 a0 有两种情况，一种是 a0 添加 b 子串的第一个元素变为 a1（子串长度加一），一种是 a0 子串保持不变。之后需要比较这两种情况才能得出最大值。而在源码中首先计算的是包含的情况 include := calculateLIS(append(currentSubsequence, remainingNums[0]), remainingNums[1:]) 这里其实可以在计算 include 之后就判断该情况得出的长度是否就是 a1 的长度加上 b1 的长度，如果是的话就可以直接返回了，因为这超过了另一种情况的最大长度（另一种情况的最大长度是 a0 的长度加上 b1 的长度 len(currentSubsequence) + len(remainingNums[1:]) ）。
1 | func calculateLIS(currentSubsequence []int, remainingNums []int) int { |
动态规划
当然上面可以在特定情况下减少一些不必要的计算，但是并不能完全避免重复计算的问题。这里其实通过递归就可以画出二叉树的形式来表示所有的可能性。先以 nums[0] 为根结点，左子树为包含 nums[1] 的情况，右子树为不包含 nums[1] 的情况。然后在左子树中又以 nums[1] 为根结点，左子树为包含 nums[2] 的情况，右子树为不包含 nums[2] 的情况。这样就可以一直递归下去，直到没有元素可选为止。而当到达叶子结点时，就可以返回当前的子串长度。而当以 nums[1] 为根结点的情况下，左子树和右子树的情况其实是重复的。以 [0,1,0,3,2,3] 为例：
在上面这颗二叉树中，每一层就表示了每判断一个元素是否该放入子串中后子串最后一个元素的状态：
- 第一层只有根结点这样 1 种状态；
- 第二层有 2 种状态；
- 第三层也只有 2 种状态；
- 第四层有 2 种状态；
- 第五层有三种状态（num[3]:3, num[1]:1, nums[0]:0）；
- 第六层有 2 种状态了（num[4]:2, num[3]:3）
如果遍历 nums 依次以数组中的每一个元素为根结点来构建这颗二叉树的话，就可以得到所有的可能性了。所以可以两个点来考虑重构之前的递归代码：
- 把计算一个元素是否放入子串作为一个阶段，每一个阶段的状态存储下来，用于下一个阶段的计算；
- 按照上面的二叉树状态来计算，每一个根结点都需要计算出所有的可能性。但除了以第一个节点作为根结点来计算外，后面所有的元素作为根节点的时候构建的状态树其实都是重复的，所以可以把之前计算过的状态存储下来，避免重复计算。
下面首先来实现用数组存储每一个阶段的状态。这里用一个 Subsequence 结构体来存储当前子串的最后一个元素和长度。然后用一个动态数组 dp 来存储每一个阶段的子串状态。每次遇到一个新的数字 nums[currentIndex]，如果它可以扩展现有的子序列，就会向 dp 中追加一个新的 Subsequence：
1 | type Subsequence struct { |
当然这个算法还不是动态规划，并且这个数组的内存占用是非常大的。主要原因如下：
- 动态数组
dp的增长：在每次迭代中，dp会存储当前起始索引startIndex下的所有可能的子序列状态。
每次遇到一个新的数字nums[currentIndex]，如果它可以扩展现有的子序列，就会向dp中追加一个新的Subsequence。
由于dp是一个动态数组，随着输入数组nums的长度增加，dp的大小可能会呈指数级增长，尤其是在输入数组接近递增序列时。
示例： 对于输入 [1, 2, 3, 4]：
dp 会存储所有可能的子序列状态：- 长度为 1 的子序列：[1]
- 长度为 2 的子序列：[1, 2], [1, 3], [1, 4]
- 长度为 3 的子序列：[1, 2, 3], [1, 2, 4], [1, 3, 4]
- 长度为 4 的子序列：[1, 2, 3, 4]
这些子序列的状态会被存储在 dp 中，导致内存占用快速增加。
- 重复计算：每次从
startIndex开始重新计算子序列，而没有利用之前计算的结果。例如，对于输入 [1, 2, 3, 4]，从startIndex = 0开始计算时，已经计算了所有以 1 开头的子序列，但从startIndex = 1开始时，又会重新计算以 2 开头的子序列，导致大量重复计算和冗余存储。 Subsequence结构体的存储开销：每个Subsequence结构体存储两个字段：value和length。这些结构体会被频繁创建并存储在dp中，进一步增加了内存占用。- 嵌套循环的复杂性：外层循环遍历
startIndex，内层循环遍历currentIndex，最内层循环遍历dp。这种三层嵌套循环会导致算法的时间复杂度和空间复杂度都非常高，接近O(n^3)。
继续以优化该算法，要减少结构体的存储开销、嵌套循环的复杂行和动态数组的增长等问题，重新审视这个问题。其实从刚才的二叉树表示的状态图就可以看出，可以从动态规划的角度考虑问题。所以需要去思考状态转移的过程。
动态转移方程
动态规划最重要的就是要理解动态转移方程，而这个题的动态规划转移之所以一开始比较难理解，其核心就是要想到：所有的递增子序列都可以看作是一个以 nums[i] 为结尾的子串。假设 nums 这个数组的长度为 n，那么就可以表示为：
在上面的公式中，P_i 表示以 nums[i] 为结尾的递增子串的集合，P0 就表示以 nums[0] 为结尾的递增子串的集合，P1 就表示以 nums[1] 为结尾的递增子串的集合，依次类推。而 P 表示所有的递增子串的集合。也就是说，P 是所有 P_i 的并集。
这非常重要，因为之前的算法和思维定势会让人不自觉地想到要从头开始计算每一个子串的状态，也就是在不自觉中把所有的递增子序列都可以看作是一个以 nums[i] 为开头的子串。
但是如果以 nums[i] 为开头的话，就会出现当需要判定某个元素 nums[j] 能够添加到该子串的时候，仍然需要去比较 nums[j] 和该子串的最后一个元素的大小，所以每一个以 nums[i] 开头的子串都需要存储其末尾的元素值，最终就会额外的内存开销过大的问题。比如在上面的二叉树中，nums[:1] 和 nums[:2] 都是以 nums[0] 为开头的子串，而 nums[1:2] 和 nums[1:3] 都是以 nums[1] 为开头的子串，但每一个子串都需要存储其末尾的元素值。
而如果将 所有的递增子序列看作是一个以 nums[i] 为结尾的递增子串的集合 的话，问题就会迎刃而解。因为这样我们写出的动态规划方程就会非常简单且易于实现。求 nums 这个数组的最长递增子序列的长度的过程就可以转换为：比较每一个以 nums[i] 为结尾的最长递增子串的长度，求出其最大值即可。而求出每一个以 nums[i] 为结尾的最长递增子串的长度就可以通过动态转移方程来实现：
令长度为
i+1、j=i-1，也就是说数组最后一个元素为nums[i]、倒数第二个元素为nums[j]
- 判断
nums[i]这个元素是否可以添加到 nums[0:j] 这个数组的所有递增子串中（而判断nums[i]是否可以添加到 “nums[0:j]这个数组的所有递增子串” 中，其实就是从以nums[0],nums[1]…nums[j]为结尾的最长递增子串中去找出所有可以添加nums[i]的子串，也就是分别判断nums[i]是否大于这些子串的结尾元素nums[0]、nums[1]…nums[j]）； - 如果存在可以添加的子串的话，
nums这个数组的最长递增子序列长度就等于 “所有可添加元素的子串长度 + 1” 后的最大值； - 如果所有子串都不可以添加的话，
nums这个数组的最长递增子序列长度就等于1（也就是nums[i]这个元素本身）；
所以这里就可以尝试写出状态转移方程：
根据状态转移方程，接下来就要思考动态规划的实现了：
- 目标：存储每一个以
nums[i]为结尾的最长递增子串的长度，然后求出其最大值，假设这个数组是dp的话，最后结果也就是max(dp(i))； - 从何处开始：因为这个问题的状态转移是从后往前进行的。也就是在计算“以
nums[i]为结尾的最长递增子串”长度的时候，已经计算过“以nums[:i-1]这个数组的所有递增子序列”了，也就是说已经计算过 “以nums[0],nums[1]…nums[i-1]为结尾的最长递增子串” 的长度了，所以就从nums[0:1]这个数组开始计算； - 如何判断：判断
nums[i]是否可以添加到nums[0:j]这个数组的所有递增子串中，其实就是从以nums[0],nums[1]…nums[j]为结尾的最长递增子串中去找出所有可以添加nums[i]的子串，也就是分别判断nums[i]是否大于这些子串的结尾元素nums[0]、nums[1]…nums[j]； - 如何存储：用一个数组
dp来存储每一个以nums[i]为结尾的最长递增子串的长度，dp[i]就表示以nums[i]为结尾的最长递增子串的长度； - 如何更新：如果
nums[i]可以添加到nums[0:j]这个数组的所有递增子串中，那么就需要更新dp[i]的值，dp[i] = max(dp(k) + 1)，也就是在dp中找到所有可以添加nums[i]的子串的长度，然后加上1（也就是nums[i]本身）； - 如何结束：当
nums这个数组的所有元素都计算完毕后，就可以返回max(dp)了。
最后实现代码如下：
1 | func max(a, b int) int { |
贪心算法&二分查找
在动态规划的实现中，时间复杂度是 O(n^2)，而空间复杂度是 O(n)。但是这个题其实可以用贪心算法和二分查找来实现，时间复杂度可以降到 O(nlogn)，空间复杂度也可以降到 O(n)。
贪心算法的核心思想是：在每一步选择中都采取在当前状态下最好或最优的选择，从而希望通过每个阶段的最优选择达到全局的最优。而这个题的贪心算法就是要找到一个递增子序列的最小结尾值。也就是，要让每一个递增子序列的最后一个元素尽可能小，这样就可以为后面的元素留出更多的空间来扩展这个递增子序列。比如在 [10, 9, 2, 5, 3, 7, 101, 18] 中：
- 长度为
1的递增子串中，[10]、[9]、[2]、[5]、[3]、[7]、[101]、[18]都是长度为1的递增子串，显然这些递增子串中末尾元素最小的就是2，也就是nums[2]； - 长度为
2的递增子串就可以以上一步的最优子串（[2]）为基础进行拓展，这其中中[2, 5]、[2, 3]、[2, 7]、[2, 101]、[2, 18]都是长度为2的递增子串。因为长度为1的递增子串中，最后一个元素的值越小，长度为2的递增子串中，最后一个元素的值可选范围就越大。那么此时选出长度为2的递增子串中最后一个元素最小的就是5，也就是nums[3]，子串为[2, 5]； - 而长度为
3的递增子串就可以以上一步的最优子串（[2, 5]）为基础进行拓展，这其中中[2, 5, 7]、[2, 5, 101]、[2, 5, 18]都是长度为3的递增子串。选出长度为3的递增子串中最后一个元素最小的就是7，也就是nums[5]，子串为[2, 5, 7]； - 依次类推，最终得到的最长递增子序列就是
[2, 3, 7, 18]，长度为4。
所以这里用贪心算法的核心就是要找到一个递增子序列的最小结尾值。也就是要让每一个递增子序列的最后一个元素尽可能小，这样就可以为后面的元素留出更多的空间来扩展这个递增子序列。
就编码而言，可以假设 tails 数组存储当前最长递增子序列的最小结尾值，且因为 tails 数组是有序的，那么就可以用二分查找来找到 tails 中第一个大于 num 的元素，然后更新 tails 中该元素为 num，而如果 num 大于 tails 中的所有元素的话，就扩展 tails 数组。最后，tails 数组的长度就是最长递增子序列的长度。下面是贪心算法和二分查找的实现：
1 | func lengthOfLIS(nums []int) int { |
最后更新 tails 的值是通过 left 来判断的，left 就是 tails 中第一个大于 num 的元素的下标，如果 left 大于等于 tails 的长度的话，就说明 num 大于 tails 中的所有元素了，就需要扩展 tails 数组。否则就更新 tails[left] 为 num。这样就可以保证 tails 数组是有序的。