面试经典题：最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1
  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

让我们用一个具体的例子来模拟最长递增子序列（LIS）的 O(nlog⁡n) 时间复杂度的 C++ 实现。

模拟步骤

  1. 初始化：
    • tail 数组用于存储当前 LIS 的末尾元素。
    • length 变量用于记录当前 LIS 的长度。
  2. 遍历数组：
    • 对于每个元素 nums[i]，根据其值与 tail 数组中的元素进行比较：
      • 如果 nums[i] 小于 tail[0]，则替换 tail[0]。
      • 如果 nums[i] 大于 tail[length - 1]，则将其添加到 tail 数组的末尾，并增加 length。
      • 否则，使用二分查找找到 tail 数组中第一个大于等于 nums[i] 的元素，并替换它。

具体模拟

假设我们有以下数组：

1
vector<int> nums = {2, 5, 3, 7, 11, 8, 10, 13, 6};
  1. 初始状态：
    • tail = [0, 0, 0, 0, 0, 0, 0, 0, 0]
    • length = 1
  2. 处理第一个元素 2：
    • tail = [2, 0, 0, 0, 0, 0, 0, 0, 0]
    • length = 1
  3. 处理第二个元素 5：
    • 5 > tail[0]，所以 tail[1] = 5
    • tail = [2, 5, 0, 0, 0, 0, 0, 0, 0]
    • length = 2
  4. 处理第三个元素 3：
    • 3 在 tail[0] 和 tail[1] 之间，二分查找找到位置 1，替换 tail[1]
    • tail = [2, 3, 0, 0, 0, 0, 0, 0, 0]
    • length = 2
  5. 处理第四个元素 7：
    • 7 > tail[1]，所以 tail[2] = 7
    • tail = [2, 3, 7, 0, 0, 0, 0, 0, 0]
    • length = 3
  6. 处理第五个元素 11：
    • 11 > tail[2]，所以 tail[3] = 11
    • tail = [2, 3, 7, 11, 0, 0, 0, 0, 0]
    • length = 4
  7. 处理第六个元素 8：
    • 8 在 tail[2] 和 tail[3] 之间，二分查找找到位置 3，替换 tail[3]
    • tail = [2, 3, 7, 8, 0, 0, 0, 0, 0]
    • length = 4
  8. 处理第七个元素 10：
    • 10 > tail[3]，所以 tail[4] = 10
    • tail = [2, 3, 7, 8, 10, 0, 0, 0, 0]
    • length = 5
  9. 处理第八个元素 13：
    • 13 > tail[4]，所以 tail[5] = 13
    • tail = [2, 3, 7, 8, 10, 13, 0, 0, 0]
    • length = 6
  10. 处理第九个元素 6：
    • 6 在 tail[1] 和 tail[2] 之间，二分查找找到位置 2，替换 tail[2]
    • tail = [2, 3, 6, 8, 10, 13, 0, 0, 0]
    • length = 6

最终，tail 数组的内容为 [2, 3, 6, 8, 10, 13, 0, 0, 0]，length 为 6。因此，最长递增子序列的长度为 6。

O(nlog(n))时间复杂度的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
    if (nums.empty()) return 0;

    vector<int> tail(nums.size(), 0);
    int length = 1; // length of LIS

    tail[0] = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        if (nums[i] < tail[0]) {
            // new smallest value
            tail[0] = nums[i];
        } else if (nums[i] > tail[length - 1]) {
            // nums[i] extends the largest subsequence
            tail[length++] = nums[i];
        } else {
            // nums[i] will become end candidate of an existing subsequence or
            // Throw away larger elements in all LIS to make room for upcoming greater elements than nums[i]
            // nums[i] will extend a subsequence and at the same time, ensure the length is maximal
            // binary search to find the position to replace
            int left = 0, right = length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (tail[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            tail[left] = nums[i];
        }
    }

    return length;
}

int main() {
    vector<int> nums = {2, 5, 3, 7, 11, 8, 10, 13, 6};
    cout << "Length of the longest increasing subsequence is " << longestIncreasingSubsequence(nums) << endl;
    return 0;
}