Longest Increasing Subsequence

300. 最长递增子序列

分析

思路
- 使用一个数组 q 来维护当前已知的递增子序列。这个数组不一定是真实的子序列，而是用于动态记录递增子序列的长度信息
- 遍历数组 nums 时，依次将当前数字插入到 q 中，保证 q 中的元素始终满足递增条件
处理策略：
- 如果当前数字 x 大于 q 的最后一个元素，则直接追加到 q 的末尾
- 否则，使用二分查找找到 q 中第一个大于或等于 x 的位置，并用 x 替换该位置的值这相当于更新子序列，使其在同样长度的情况下更容易扩展
返回结果：
- 最终数组 q 的长度即为最长递增子序列的长度

时间复杂度

遍历数组时，每个元素需要执行一次二分查找，二分查找的复杂度为 O(logn)

总时间复杂度 O(nlogn)

空间复杂度

空间复杂度为 O(n)

C++代码

 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


class Solution
{
public:
    int lengthOfLIS(vector<int>& nums)
    {
        std::vector<int> q;  // 用于记录递增子序列的数组
        for (int x : nums)
        {
            if (q.empty() || x > q.back())  // 如果当前数字大于子序列末尾元素
                q.push_back(x);  // 直接追加
            else
            {
                // 使用二分查找定位
                int l = 0, r = q.size() - 1;
                while (l < r)
                {
                    int mid = (l + r) >> 1;  // 中间位置
                    if (x <= q[mid])  // 如果当前数字小于等于 q[mid]
                        r = mid;  // 缩小右边界
                    else
                        l = mid + 1;  // 缩小左边界
                }
                q[r] = x;  // 替换第一个大于等于 x 的位置
            }
        }
        return q.size();  // q 的长度即为最长递增子序列的长度
    }
};