Fork me on GitHub

300.最长上升子序列

发表于 | 分类于 ， | 次阅读
字数统计: 349 | 阅读时长 ≈ 1

基本思路

我们可以使用贪心来看，要想我们的序列尽可能地长，我们需要我们的序列上升得尽可能地慢。我们定义一个序列$d$，$d[i]$表示当前长度为$i+1$的上升子序列的末尾元素最小为$d[i]$，只有子序列末尾元素尽可能的小，后面才会有更多的数能插入到尽可能靠前的位置，从而形成尽可能长的序列。

当我们遇到一个数$nums[i]$，我们和序列$d$的最后一个元素进行比较，如果比这个元素小，那么就直接插入到序列$d$的末尾，否则，我们需要找到序列中比$nums[i]$大的最小元素，这里有个问题就是，如果序列$d$中有和$nums[i]$值一样的元素，那么此时不需要插入，这里需要特判一下。

代码

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
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        vector<int> d(n+1 , 0);
        d[1] = nums[0];
        int len = 1;
        for(int i = 1 ; i<n ; ++i){
            if(nums[i] > d[len]) d[++len] = nums[i];
            else {
                int left = 1 , right = len;
                while(left <= right){
                    int mid = (left + right) / 2;
                    if(d[mid] > nums[i]){
                        right = mid - 1;
                    }
                    else left = mid + 1;
                }
                if(d[left - 1] < nums[i]){ // 特判一下
                    d[left] = nums[i];
                }
            }
        }
        return len;
    }
};