在算法面试中,最长上升子序列(Longest Increasing Subsequence, LIS)是一道经典且富有挑战性的题目。它不仅考察了面试者对动态规划、二分查找等基础算法的理解,还检验了他们在面对复杂问题时将问题拆解、优化算法的能力。本章节将详细解析最长上升子序列的概念、解法,以及如何通过不同策略优化算法效率,帮助读者在面试中游刃有余地应对此类问题。
最长上升子序列问题可以描述为:给定一个无序的整数数组(nums),找到并返回数组中最长上升子序列的长度。注意,这里的子序列并不是子数组,它可以不连续,但必须保持相对顺序。例如,对于数组 [10, 9, 2, 5, 3, 7, 101, 18]
,其最长上升子序列为 [2, 3, 7, 101]
,长度为 4。
解决最长上升子序列问题主要有两种常用方法:动态规划(Dynamic Programming, DP)和二分查找优化(基于贪心+二分查找)。下面我们将分别介绍这两种方法。
思路分析:
动态规划是解决此类问题的直观方法。我们定义一个数组 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
数组中的最大值即为所求的最长上升子序列长度。
代码实现:
def lengthOfLIS(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n # 初始化dp数组,每个元素至少可以单独构成一个长度为1的子序列
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
时间复杂度:O(n^2),其中 n 是数组的长度。由于有两层嵌套循环,所以时间复杂度为平方级别。
空间复杂度:O(n),用于存储 dp 数组。
思路分析:
虽然动态规划能够解决问题,但在面对大数据量时,其性能可能成为瓶颈。一种更优的解法是利用贪心算法结合二分查找来优化。我们维护一个数组 tails
,其中 tails[i]
表示长度为 i+1
的所有上升子序列中,末尾元素最小的那个子序列的末尾元素。遍历数组 nums
,对于每个元素 nums[i]
,我们使用二分查找在 tails
中找到第一个不小于 nums[i]
的位置 pos
,如果 pos
等于 tails
的长度,说明找到了一个更长的上升子序列,直接添加到 tails
末尾;否则,更新 tails[pos]
为 nums[i]
(保持子序列末尾元素尽可能小,以便后续可能的扩展)。
代码实现:
def lengthOfLIS(nums):
if not nums:
return 0
tails = []
for num in nums:
if not tails or num > tails[-1]:
tails.append(num)
else:
left, right = 0, len(tails) - 1
while left <= right:
mid = (left + right) // 2
if tails[mid] < num:
left = mid + 1
else:
right = mid - 1
tails[left] = num
return len(tails)
时间复杂度:O(nlogn),其中 n 是数组的长度。每个元素 nums[i]
最多被插入到 tails
数组一次,且每次插入都通过二分查找确定位置,因此时间复杂度为线性对数级别。
空间复杂度:O(n),用于存储 tails
数组,其大小最多为 n(虽然实际大小通常远小于 n)。
最长上升子序列问题是算法面试中的一道经典题目,通过动态规划和二分查找优化两种方法的介绍,我们不仅掌握了解决此类问题的基本技巧,还学习了如何在不同场景下选择合适的算法策略。在面试准备过程中,建议读者不仅要熟练掌握这两种解法,还要能够灵活应对问题的各种变体,以及理解其背后的算法思想和优化思路。