AcWing 896. LIS(单调栈+二分)
原题链接
简单
//O(nlogn)
#include<iostream>
using namespace std;
const int N = 100010;
//单调栈s[i]维护长度为i的LIS末尾值,栈的指针p大小就是元素个数,即LIS
//贪心:末尾值尽可能小,更易插入下一个数
int n, a[N], s[N], p;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
s[0] = -2e9;//第一个数可能是大负数
for (int i = 1; i <= n; i++)
if (a[i] > s[p])//当前元素大于栈顶元素,则入栈
s[++p] = a[i];
else if(a[i] == s[p])//小优化:不用再二分一遍
continue;
//否则栈中一定存在j满足s[j - 1]<=a[i]<s[j]
else
{
int l = 1, r = p;//二分找栈中>=a[i]的最小一个数
while (l < r)
{
int mid = l + r >> 1;
if (s[mid] >= a[i])
r = mid;
else l = mid + 1;
}
s[l] = a[i];
}
cout << p << endl;
return 0;
}