- 正确答案：最长上升子序列（Longest Increasing Subsequence, LIS）问题的经典解法有两种：动态规划（DP）解法，时间复杂度为 O(n²)；以及基于二分查找的优化解法，时间复杂度为 O(n log n)。下面分别给出两种解法的详细说明和实现。 - 解答思路： 1. 首先理解“最长上升子序列”的定义：在给定数组中，找出一个子序列（不要求连续），使得该子序列中的元素严格递增，并且长度最长。 2. 使用动态规划的基本思路是：定义 dp[i] 表示以第 i 个元素结尾的最长上升子序列的长度。对于每个 i，遍历前面所有 j < i 的位置，如果 nums[j] < nums[i]，则可以将 nums[i] 接在以 nums[j] 结尾的 LIS 后面，从而更新 dp[i]。 3. 为了优化到 O(n log n)，我们使用一个辅助数组 tails，其中 tails[k] 表示长度为 k+1 的所有上升子序列中，最小的结尾元素。通过维护这个数组，并使用二分查找来决定当前元素应插入的位置，可以实现更优的时间复杂度。 - 深度知识讲解：一、动态规划解法（O(n²)）核心思想： - 定义状态：dp[i] = 以 nums[i] 结尾的 LIS 的长度 - 状态转移方程：dp[i] = max(dp[i], dp[j] + 1)，其中 j < i 且 nums[j] < nums[i] - 初始条件：每个 dp[i] = 1（每个元素本身构成一个长度为1的上升子序列） - 最终结果：max(dp[0], dp[1], ..., dp[n-1]) 数据结构：一维数组 dp，大小为 n 示例： nums = [10, 9, 2, 5, 3, 7, 101, 18] dp = [1, 1, 1, 2, 2, 3, 4, 4] LIS 长度为 4，对应子序列如 [2,3,7,18] 二、二分查找优化解法（O(n log n)）关键观察： - 我们并不关心具体的子序列是什么，只关心长度。 - 维护一个数组 tails，其中 tails[len] 表示长度为 len+1 的上升子序列中，最小的末尾元素。 - 这个 tails 数组是严格递增的，因此可以使用二分查找来定位插入位置。为什么 tails 是递增的？假设存在 i < j 但 tails[i] >= tails[j]，这意味着一个较短的子序列的结尾比更长的还大，这与“最小结尾”的定义矛盾。因此 tails 是单调递增的。操作逻辑：对每个 nums[i]： - 如果 nums[i] 大于 tails 最后一个元素，直接追加，LIS 长度+1 - 否则，在 tails 中找到第一个 >= nums[i] 的位置，用 nums[i] 替换它（保持最小结尾性质）注意：替换并不会改变实际子序列，但维护了构造更长 LIS 的潜力。数据结构： - tails 数组，动态维护 - 使用二分查找（lower_bound）找到插入位置三、底层原理与算法思想： - 动态规划：状态设计 + 状态转移 - 贪心思想：在相同长度下，结尾越小越好，留给后续扩展的空间越大 - 二分查找：利用单调性加速搜索四、边界情况： - 数组为空：返回 0 - 数组只有一个元素：返回 1 - 所有元素相等：LIS 长度为 1（严格递增） - 严格递减序列：LIS 长度为 1 - 代码示例（C++ 风格，纯文本）： // 方法一：动态规划 O(n^2) int lengthOfLIS(vector& nums) { if (nums.empty()) return 0; int n = nums.size(); vector dp(n, 1); // 初始化每个位置的 LIS 长度为 1 int maxLength = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } maxLength = max(maxLength, dp[i]); } return maxLength; } // 方法二：二分查找优化 O(n log n) int lengthOfLIS(vector& nums) { if (nums.empty()) return 0; vector tails; // tails[i] 表示长度为 i+1 的 LIS 的最小结尾元素 for (int x : nums) { // 二分查找第一个 >= x 的位置 int left = 0, right = tails.size(); while (left < right) { int mid = left + (right - left) / 2; if (tails[mid] < x) { left = mid + 1; } else { right = mid; } } // 如果 left == tails.size()，说明 x 比所有元素都大，追加 if (left == tails.size()) { tails.push_back(x); } else { tails[left] = x; // 替换，保持最小结尾 } } return tails.size(); } - 扩展知识点： 1. 如何输出具体的 LIS 序列？ - 在 DP 方法中，可以通过记录 parent 数组（每个位置的前驱）来重构路径。 - 优化方法中无法直接重构，因为 tails 不保存完整路径。 2. 变种问题： - 最长非递减子序列（允许相等）：将严格比较 < 改为 <= - 最长连续上升子序列：要求连续，可用滑动窗口解决 - 二维 LIS（如俄罗斯套娃信封问题）：先排序，再对第二维求 LIS 3. 实际应用场景： - 生物信息学中的序列比对 - 股票交易问题中的最长盈利区间 - 排序算法性能分析 4. 算法对比总结： - 时间复杂度：O(n^2) vs O(n log n) - 空间复杂度：都是 O(n) - 是否可重构解：DP 可以，二分优化法一般不行 - 适用场景：数据量小时可用 DP，大数据量必须用优化法 - 总结： LIS 是经典动态规划问题，考察对状态定义、转移方程、贪心优化和二分查找的综合理解。面试中通常要求写出 O(n^2) 解法，若能进一步提出 O(n log n) 解法将极大加分。建议掌握两种方法，并理解其背后的贪心思想和单调性原理。

滴滴 秋招二面

全站热榜

创作者周榜

滴滴秋招二面