57 最长递增子序列

给你一个整数数组 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
• $-10^4$ <= nums[i] <= $10^4$

进阶：

你能将算法的时间复杂度降低到 $O(nlog(n))$ 吗?

题解1 DP $O(n^2)$

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int maxN = INT_MIN;
        /**
        dp[i] : i处数值对应的最长子序列长度
        **/
        for(int i = 1; i < nums.size(); i++){    
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j]+1);
            }
            maxN = max(maxN, dp[i]);
        }
        return maxN == INT_MIN ? 1 : maxN;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题解2 贪心+二分搜索（ref. from Leetcode）$O(nlog(n))$

“从左到右（序列顺序），维护一个每个元素尽可能小的LIS备选集合S”

每个元素尽可能小，这样更可能在末尾加上一个新的值，构成一个更大的LIS

只增加（add）和替换（swap），因此完成遍历后S的长度一定等于LIS的长度,部分元素可能被你替换掉了，所以在整个遍历过程中，这个集合S可能并不是LIS本身,尽管如此，LIS的元素一定曾出现在S中（但可能在遍历过程中被swap覆盖掉了）

鼓掌！！这个思想好棒

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(1 == nums.size()) return 1;
        // p[i]: 长度为i的最长上升子序列的末尾元素最小值
        vector<int> p(nums.size()+1, 0);
        int len = 1;
        p[len] = nums[0];
        
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] > p[len]){
                len ++;
                p[len] = nums[i];
            }else{
                // 在i位置不用遍历得到dp值
                // 长度=len+1的子序列的最小值 > nums[i]，为了保持p的递增，需要修改某个位置的值
                // 用二分找到最近的j, 满足p[j] < nums[i] < p[j+1]
                // s.t. p[j+1] = nums[i];
                // 如果找不到, 说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                int left = 1;
                int right = len;
                int pos = 0;
                // 最希望的是改p[len], 所以判断条件 有 =
                // 实际上是想不用遍历，用二分检查一遍 nums[i]是不是大于len+1情况里的倒数第二个最大的数吧
                while(left <= right){
                    int mid = (left+right) >> 1;
                    // 找到了j
                    if(nums[i] > p[mid]){
                        pos = mid;
                        left = mid+1;
                    }  
                    else{
                        right = mid-1;
                    }
                }
                p[pos + 1] = nums[i];
            }
        }
        return len;
    }
};
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