896. 最长上升子序列 II(贪心+队列)

896. 最长上升子序列 II(贪心+队列)

 

 本题的数据范围是100000，如果用动态规划的思想肯定会超时

我们想到了贪心+队列，时间复杂度O(nlogn)

思想如下：

一串数字，对于3来说，如果以他作为最长上升子序列的开头的话，不如以1作为最长上升子序列的开头，因为1更小，他的后面可以容纳更多的上升子序列

 那么有了这个思想，我们就可以维护一个队列，如果一个数比队列中的某一个数更小的话，我们就可以把他插入这个队列中替换原来的位置，变成以该数字结尾的一个上升子序列

但是这样子会破坏原来的序列，我们只需要只需要用这个长度更新一下，不断枚举，然后更新最长的上升子序列长度是多少就行了

问题：为什么可以用二分

注意这里用的是寻找最后一个比a[i]小的数字，插入进行替换。

所以可以维护一个最长上升子序列，这个子序列是单调的，所以可以使用二分的思想

 样例如下

 

 

 

#include 
#include 
using namespace std;
const int N=1e5+10;
int a[N];
int q[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i>a[i];  
    q[0]=-2e9;
    int len=0;
    //如果找不到,就在最后一个地方插入
    //如果能找到就替换
    for(int i=0;i>1;
            if(q[mid]