本文共 1767 字，大约阅读时间需要 5 分钟。
长度最长递增子序列（LIS）问题解决方案
在线讨论区中，一道经典的算法题引发了热议：如何找到一个数组中的最长递增子序列（LIS）。这个问题不仅考察了算法设计能力，还要求程序高效处理较大的数据量。本文将详细介绍一个优化后的解决方案。
针对这个问题，我们采用动态规划（DP）结合二分查找的方法。具体步骤如下：
初始化一个空列表 dp，用于记录当前遍历过的元素的最长递增子序列的长度。
遍历数组中的每个元素 nums[i]：
nums[j]（其中 j < i），如果当前元素 nums[i] 大于 nums[j]，则更新 dp[i] 为 dp[j] + 1。dp 中第一个大于等于 nums[i] 的位置 idx，如果 idx 不存在，则将 nums[i] 添加到 dp 中；否则，将 nums[i] 替换 dp[idx]。这种方法充分利用了排序查找的特性，将时间复杂度优化至 O(n log n)，大大提高了处理大规模数据的效率。
以下是该算法在实际应用中的示例：
from typing import Listfrom bisect import bisect_leftclass Solution: def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 dp = [] for num in nums: idx = bisect_left(dp, num) if idx == len(dp): dp.append(num) else: dp[idx] = num return len(dp)print(Solution().lengthOfLIS([3, 2, 1, 1, 2]))
最大信封问题解决方案
在数据处理领域，另一个常见的算法问题是“最大信封问题”。给定一组信封，每个信封有两个维度的尺寸，我们的目标是找到能装下所有信封的最小信封尺寸。这个问题可以通过将问题转化为长度最长递增子序列（LIS）问题来解决。
解决方法如下：
将信封按照第一个维度从小到大排序（如果第一个维度相同时，按照第二个维度从大到小排序）。
提取所有信封的第二个维度，形成一个新的数组，计算这个数组的最长递增子序列的长度。
这个算法的核心思想是：最小的信封必须能够包含所有信封，因此它必须具备最大的第一个维度和最大的第二个维度。通过排序和LIS算法，我们可以高效地找到最优解。
以下是该算法在实际应用中的示例：
from typing import Listfrom bisect import bisect_leftclass Solution: def maxEnvelopes(self, arr: List[List[int]]) -> int: # 按第一个维度升序排列，第二个维度降序排列 arr.sort(key=lambda x: (x[0], -x[1])) def lis(nums): dp = [] for num in nums: idx = bisect_left(dp, num) if idx == len(dp): dp.append(num) else: dp[idx] = num return len(dp) # 提取第二个维度并计算LIS return lis([i[1] for i in arr])print(Solution().maxEnvelopes([[5,4],[6,4],[6,7],[2,3]]))
转载地址：http://ffgfk.baihongyu.com/