[ACwing]896. 最长上升子序列 II

算法标签 贪心 二分

题目简叙

思路

维护一个单调栈，如果是大于栈末尾元素就插入，形成单调栈，否则就找到第一个大于的元素进行替换，通过这种方式计算最长子序列的长度

代码

#include<iostream>

using namespace std;

int n;
const int N=1e5+10;
int stk[N];//模拟单调栈
int arr[N];//数据
int cnt;

int find(int x){//找到第一个栈里数据大于X的
    int l = 1, r = cnt; 
    while(l < r) {
        int mid = l + r >> 1;
        if(stk[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return l;
}

int main(){
    cin>>n;
    
    for(int i = 1; i <= n; i ++)cin>>arr[i];
    
    stk[++cnt]=arr[1];//初始化第一个数据
    
    for(int i = 2; i <= n; i ++)//处理之后的数据
        arr[i]>stk[cnt]?stk[++cnt]=arr[i]:stk[find(arr[i])]=arr[i];//如果是大于栈末尾元素就插入，形成单调栈，否则就找到第一个大于的元素进行替换
    
    cout<<cnt;
    
    return 0;
}

AC记录