算法基础之最长上升子序列 II

最长上升子序列 II

• 核心思想：不去遍历全部的数据(会有冗余)

  • 用vector模拟栈 ①如果该元素大于栈顶元素,将该元素入栈

  • ②替换掉第一个大于或者等于这个数字的那个数（二分）

    

•   #include<iostream>
    #include<algorithm>
    #include<vector>
    
    using namespace std;
    int n;
    
    int main()
    {
        cin>>n;
        vector<int> a(n),stk;  //a(n) 必须这么写才能用a[]操作数据
        for(int i=0;i<n;i++) cin>>a[i];  //输入数据
        
        stk.push_back(a[0]);  //a[0] 入栈初始化
        for(int i=1;i<n;i++)  //从a[1] 开始
        {
            if(a[i] > stk.back()) stk.push_back(a[i]);  //大于栈顶元素 直接加进去
            else
            {	//二分 lower_bound从头找出>=a[i]的第一个元素 将其替换(函数返回指针 解引用)
                *lower_bound(stk.begin(),stk.end(),a[i]) = a[i];
            }
        }
        
        cout<<stk.size()<<endl;  //stk内容不一定是目标子序列 但是长度没问题
    }
  

  • 注意a的定义写法
    • 

• 参考题解 ： https://www.acwing.com/solution/content/3783/