当前位置:  首页>> 技术小册>> 算法面试通关 50 讲

49 | 面试题:最长上升子序列

在算法面试中,最长上升子序列(Longest Increasing Subsequence, LIS)是一道经典且富有挑战性的题目。它不仅考察了面试者对动态规划、二分查找等基础算法的理解,还检验了他们在面对复杂问题时将问题拆解、优化算法的能力。本章节将详细解析最长上升子序列的概念、解法,以及如何通过不同策略优化算法效率,帮助读者在面试中游刃有余地应对此类问题。

一、问题定义

最长上升子序列问题可以描述为:给定一个无序的整数数组(nums),找到并返回数组中最长上升子序列的长度。注意,这里的子序列并不是子数组,它可以不连续,但必须保持相对顺序。例如,对于数组 [10, 9, 2, 5, 3, 7, 101, 18],其最长上升子序列为 [2, 3, 7, 101],长度为 4。

二、解法概览

解决最长上升子序列问题主要有两种常用方法:动态规划(Dynamic Programming, DP)和二分查找优化(基于贪心+二分查找)。下面我们将分别介绍这两种方法。

2.1 动态规划解法

思路分析
动态规划是解决此类问题的直观方法。我们定义一个数组 dp,其中 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。遍历数组 nums,对于每个元素 nums[i],再向前遍历所有 j < i 的位置,如果 nums[j] < nums[i],则说明 nums[i] 可以接在 nums[j] 后面形成一个更长的上升子序列。此时,我们更新 dp[i]dp[j] + 1 和当前 dp[i] 中的较大值。最终,dp 数组中的最大值即为所求的最长上升子序列长度。

代码实现

  1. def lengthOfLIS(nums):
  2. if not nums:
  3. return 0
  4. n = len(nums)
  5. dp = [1] * n # 初始化dp数组,每个元素至少可以单独构成一个长度为1的子序列
  6. for i in range(1, n):
  7. for j in range(i):
  8. if nums[j] < nums[i]:
  9. dp[i] = max(dp[i], dp[j] + 1)
  10. return max(dp)

时间复杂度:O(n^2),其中 n 是数组的长度。由于有两层嵌套循环,所以时间复杂度为平方级别。

空间复杂度:O(n),用于存储 dp 数组。

2.2 二分查找优化解法

思路分析
虽然动态规划能够解决问题,但在面对大数据量时,其性能可能成为瓶颈。一种更优的解法是利用贪心算法结合二分查找来优化。我们维护一个数组 tails,其中 tails[i] 表示长度为 i+1 的所有上升子序列中,末尾元素最小的那个子序列的末尾元素。遍历数组 nums,对于每个元素 nums[i],我们使用二分查找在 tails 中找到第一个不小于 nums[i] 的位置 pos,如果 pos 等于 tails 的长度,说明找到了一个更长的上升子序列,直接添加到 tails 末尾;否则,更新 tails[pos]nums[i](保持子序列末尾元素尽可能小,以便后续可能的扩展)。

代码实现

  1. def lengthOfLIS(nums):
  2. if not nums:
  3. return 0
  4. tails = []
  5. for num in nums:
  6. if not tails or num > tails[-1]:
  7. tails.append(num)
  8. else:
  9. left, right = 0, len(tails) - 1
  10. while left <= right:
  11. mid = (left + right) // 2
  12. if tails[mid] < num:
  13. left = mid + 1
  14. else:
  15. right = mid - 1
  16. tails[left] = num
  17. return len(tails)

时间复杂度:O(nlogn),其中 n 是数组的长度。每个元素 nums[i] 最多被插入到 tails 数组一次,且每次插入都通过二分查找确定位置,因此时间复杂度为线性对数级别。

空间复杂度:O(n),用于存储 tails 数组,其大小最多为 n(虽然实际大小通常远小于 n)。

三、优化与变体

  • 空间优化:虽然二分查找优化解法已经相当高效,但如果对空间有极致要求,可以尝试使用其他数据结构(如平衡二叉搜索树)来替代数组,以在保持时间效率的同时减少空间占用。
  • 变体问题:最长上升子序列问题有很多变体,如求最长公共上升子序列(Longest Common Increasing Subsequence, LCIS)、最长不下降子序列(Longest Non-decreasing Subsequence, LNDS)等。这些问题虽然基本思路相似,但细节处理上有所不同,需要具体问题具体分析。
  • 应用场景:最长上升子序列问题不仅限于算法面试,还广泛应用于生物信息学、经济学等多个领域,如基因序列分析、股票价格预测等。

四、总结

最长上升子序列问题是算法面试中的一道经典题目,通过动态规划和二分查找优化两种方法的介绍,我们不仅掌握了解决此类问题的基本技巧,还学习了如何在不同场景下选择合适的算法策略。在面试准备过程中,建议读者不仅要熟练掌握这两种解法,还要能够灵活应对问题的各种变体,以及理解其背后的算法思想和优化思路。


该分类下的相关小册推荐: