[数据结构与算法]Leetcode 300. 最长递增子序列

本题链接

题目

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路 1：动态规划

遍历数组的过程中维护数组 dp，dp[i] 的含义是以 nums[i] 结尾的最长严格递增子序列的长度。那么对于 nums[i]，需要遍历所有前面的元素 nums[j]（$0<=j<i$），如果出现有比 nums[i] 小的元素 nums[j]，就说明 dp[j]+1 是备选的 dp[i]，所有备选值中的最大值就是 dp[i]

时间复杂度：$O(n^2)$
空间复杂度：$O(n)$

C++ 代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty())
            return 0;
        // dp[i]表示nums[0]到nums[i]这个区间中
        // 必须包含nums[i]在内的最长严格递增子序列的长度
        // 最终答案就是dp中的最大值
        vector<int> dp(nums.size());
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            int maxLen = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    maxLen = max(dp[j] + 1, maxLen);
                }
            }
            dp[i] = maxLen;
        }
        int ans = 0;
        for (int num : dp) {
            ans = max(num, ans);
        }
        return ans;
    }
};

思路 2：贪心 + 二分（minTail 数组）

构建并维护一个 minTail 数组，minTail[i] 的含义是长度为 $i+1$ 的上升子序列，其末尾最小是多少。该数组初始只包含一个元素 nums[0]，然后从 nums[1] 开始遍历数组：

• 如果遇到比 minTail.back() 更大的 nums[i]，直接添加到 minTail 数组的末尾
• 否则就在 minTail 数组中二分搜索找到第一个大于等于 nums[i] 的数，用 nums[i] 替换

因为 minTail 数组是递增的，所以可以进行二分搜索。这里只写实现的思路，递增性质的证明以及具体例子在官方题解中有。

需要注意的是最后 minTail 数组的长度就是最长递增子序列的长度，但是数组本身不是合法的最长递增子序列，这是 minTail[i] 的含义决定的。

时间复杂度：$O(n\log n)$
空间复杂度：$O(n)$

C++ 代码

class Solution {
public:
    int findFirstGreaterEqual(const vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1, mid;
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (nums[mid] >= target)
                hi = mid;
            else
                lo = mid + 1;
        }
        if (nums[lo] >= target)
            return lo;
        else
            return -1;
    }

    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty())
            return 0;
        vector<int> minTail{nums[0]};
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > minTail.back()) {
                minTail.push_back(nums[i]);
            } else {
                int replaceIndex = findFirstGreaterEqual(minTail, nums[i]);
                if (replaceIndex >= 0)
                    minTail[replaceIndex] = nums[i];
            }
        }
        return minTail.size();
    }
};