LeetCode 300 - Longest Increasing Subsequence

󰃭 2024-12-14

核心思路

不同于传统 DP 解法需要通过 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度并逐个比较来获取 O(n²) 的复杂度，Binary Search 方法的核心思想是构建一个额外的 辅助数组（我们常称为 tails），用来动态维护在逐步遍历原序列时所能获得的一些「中间状态」。这些中间状态帮助我们使用二分搜索快速确定下一个元素应该放在什么位置。

tails 数组的含义

tails[k] 表示在遍历到当前元素为止，所有长度为 k+1 的递增子序列中最小的末尾值。这里「长度为 k+1 的递增子序列」可能不止一个，我们只关心其结尾最小的那个值，因为这个值越小，它就越有潜力让后面出现更长的递增子序列。

也就是说，在构建过程中，tails 数组的长度始终是当前找到的最长递增子序列长度，而 tails 中的值是各种长度子序列的最优结尾代表。

算法步骤

假设输入数组为 nums：

  1. 初始化一个空的 tails 数组（开始时它是空的）。

  2. 从左到右遍历原数组 nums 的每个元素 x：

    • 使用二分搜索在 tails 数组中寻找第一个大于等于 x 的元素的位置。
      • 若找不到（即 x 大于所有 tails 中的元素），则将 x 追加到 tails 的末尾。这意味着我们找到了一个更长的递增子序列。
      • 若找到位置 pos，则用 x 替换 tails[pos]。这样做是为了使得长度为 pos+1 的递增子序列的末尾元素尽可能小，从而更容易在后续遇到更大的数时扩展出更长的序列。

  3. 遍历结束后，tails 的长度即为最长递增子序列的长度。

直觉

  • 在 tails 中替换的过程确保了对于相同的子序列长度，我们总是保留一个更小的可能结尾元素。这样后续的元素更有机会在此序列基础上增长。
  • tails 始终保持有序（因为我们是按照递增子序列长度不断构建的），这使得我们能够使用二分搜索快速定位新元素的插入位置，从而将复杂度控制在 O(n log n)。

复杂度

  • 对于每个元素，我们通过二分搜索在 tails 中定位插入点，该过程复杂度为 O(log n)。
  • 整个过程对 n 个元素进行相同操作，所以总体复杂度为 O(n log n)，这比传统 DP 的 O(n²) 有显著优化。

例

假设 nums = [10, 9, 2, 5, 3, 7, 101, 18]。

  • 初始：tails = []
  • 处理 10：
    • tails 为空，在 tails 中找不到大于等于 10 的元素，将 10 加入。
    • tails = [10] （表示目前最长递增子序列长度为 1，其最优末尾值为 10）
  • 处理 9：
    • 在 tails = [10] 中寻找大于等于9的元素，10 ≥ 9，于是将 tails[0] 替换为 9。
    • tails = [9] （长度为1的序列末尾值更新为更小的9，对后续扩展更有利）
  • 处理 2：
    • 在 tails = [9] 中寻找大于等于2的元素，9 ≥ 2，替换之。
    • tails = [2]
  • 处理 5：
    • 在 tails = [2] 中寻找大于等于5的元素，没有，5 > 2，将 5 加入末尾。
    • tails = [2, 5] （现在我们有一个长度为1的最优末尾是2，长度为2的最优末尾是5）
  • 处理 3：
    • 在 tails = [2, 5] 中寻找大于等于3的元素，第一个大于等于3的元素是5（索引1处）。
    • 替换后 tails = [2, 3] （长度为2的子序列最优末尾从5降低为3）
  • 处理 7：
    • 在 tails = [2, 3] 中寻找大于等于7的元素，没有，7 > 3，将 7 加入。
    • tails = [2, 3, 7]
  • 处理 101：
    • 在 tails = [2, 3, 7] 中寻找大于等于101的元素，没有，101 > 7，加入。
    • tails = [2, 3, 7, 101]
  • 处理 18：
    • 在 tails = [2, 3, 7, 101] 中寻找大于等于18的元素，101 ≥ 18，在位置3处替换。
    • tails = [2, 3, 7, 18]

最终 tails 的长度是4，对应最长递增子序列长度为4（例如 [2, 3, 7, 18] 或 [2, 5, 7, 18] 等）。

代码示例（c++）


int lenOfLIS(vector<int> &nums) {
    std::vector<int> tails;
    for(auto const &i : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), i);
        if(it == nums.end()) tails.push_back(i);
        else *it = i;
    }
    return tails.size();
}

Tags: #LeetCode