第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0673. 最长递增子序列的个数

题目地址(673. 最长递增子序列的个数)

题目描述

1
给定一个未排序的整数数组,找到最长递增子序列的个数。
2
3
示例 1:
4
5
输入: [1,3,5,4,7]
6
输出: 2
7
解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
8
示例 2:
9
10
输入: [2,2,2,2,2]
11
输出: 5
12
解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。
13
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
Copied!

前置知识

  • 动态规划

公司

  • 暂无

思路

这道题其实就是 最长上升子序列(LIS) 的变种题。如果对 LIS 不了解的可以先看下我之前写的一篇文章穿上衣服我就不认识你了?来聊聊最长上升子序列,里面将这种题目的套路讲得很清楚了。
回到这道题。题目让我们求最长递增子序列的个数,而不是通常的最长递增子序列的长度。 因此我想到使用另外一个变量记录最长递增子序列的个数信息即可。类似的套路有股票问题,这种问题的套路在于只是单独存储一个状态以无法满足条件,对于这道题来说,我们存储的单一状态就是最长递增子序列的长度。那么一个自然的想法是不存储最长递增子序列的长度,而是仅存储最长递增子序列的个数可以么?这是不可以的,因为最长递增子序列的个数 隐式地条件是你要先找到最长的递增子序列才行。
如何存储两个状态呢?一般有两种方式:
  • 二维数组 dp[i][0] 第一个状态 dp[i][1] 第二个状态
  • dp1[i] 第一个状态 dp2[i] 第二个状态
使用哪个都可以,空间复杂度也是一样的,使用哪种看你自己。这里我们使用第一种,并且 dp[i][0] 表示 以 nums[i] 结尾的最长上升子序列的长度,dp[i][1] 表示 以 nums[i] 结尾的长度为 dp[i][0] 的子序列的个数。
明确了要多存储一个状态之后,我们来看下状态如何转移。
LIS 的一般过程是这样的:
1
for i in range(n):
2
for j in range(i + 1, n):
3
if nums[j] > nums[i]:
4
# ...
Copied!
这道题也是类似,遍历到 nums[j] 的时候往前遍历所有的 满足 i < j 的 i。
  • 如果 nums[j] <= nums[i], nums[j] 无法和前面任何的序列拼接成递增子序列
  • 否则说明我们可以拼接。但是拼接与否取决于拼接之后会不会更长。如果更长了就拼,否则不拼。
上面是 LIS 的常规思路,下面我们加一点逻辑。
  • 如果拼接后的序列更长,那么 dp[j][1] = dp[i][1] (这点容易忽略)
  • 如果拼接之后序列一样长, 那么 dp[j][1] += dp[i][1]。
  • 如果拼接之后变短了,则不应该拼接。

关键点解析

代码

代码支持: Python
1
class Solution:
2
def findNumberOfLIS(self, nums: List[int]) -> int:
3
n = len(nums)
4
# dp[i][0] -> LIS
5
# dp[i][1] -> NumberOfLIS
6
dp = [[1, 1] for _ in range(n)]
7
longest = 1
8
for i in range(n):
9
for j in range(i + 1, n):
10
if nums[j] > nums[i]:
11
if dp[i][0] + 1 > dp[j][0]:
12
dp[j][0] = dp[i][0] + 1
13
# 下面这行代码容易忘记,导致出错
14
dp[j][1] = dp[i][1]
15
longest = max(longest, dp[j][0])
16
elif dp[i][0] + 1 == dp[j][0]:
17
dp[j][1] += dp[i][1]
18
return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)
Copied!
复杂度分析
令 N 为数组长度。
  • 时间复杂度:$O(N^2)$
  • 空间复杂度:$O(N)$

扩展

这道题也可以使用线段树来解决,并且性能更好,不过由于不算是常规解法,因此不再这里展开,感兴趣的同学可以尝试一下。
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。