最长上升子序列优化就是：贪心+二分

【单调栈的思想：长度一样，但值小意味适用范围更广】

贪心+二分优化:对于长度为1，2…的序列，只需要保存长度最后一个最小值，用q[]数组保存，下标为长度，里面的值为当前长度的最小值

重点 理解这句话 : 用q[]数组保存，下标为长度，里面的值为最小值

#include <iostream>

using namespace std;

const int N = 1000010;

int n;
int a[N];
int q[N];

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];

    q[0] = -2e9; // 哨兵
    int len = 0; // 最长上升子序列的长度
    for(int i=1;i<=n;i++)
    {
        int l = 0 ,r = len;
        while(l < r)
        {
            int mid = l + r  + 1>> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len,r + 1);
        q[r + 1] = a[i];
    }

    cout << len << endl;

    return 0;
}

运用STL

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

const int N = 100010;

vector<int> stk; // 模拟堆栈

int main()
{
    int n;
    cin >> n;

    for(int i=0;i<n;i++)
    {
        int x;
        cin >> x;
        if(stk.empty() || x > stk.back()) stk.push_back(x); // 如果栈为空或者当前元素大于栈顶元素，入栈
        else // 替换掉第一个大于或等于(lower_bound)这个数字的那个数
        {
            *lower_bound(stk.begin(),stk.end(),x) = x;
        }
    }

    cout<<stk.size();

    return 0;
}