题解中最难理解的地方在于栈中序列虽然递增，但是每个元素在原串中对应的位置其实可能是乱的，那为什么这个栈还能用于计算最长子序列长度？
实际上这个栈【不用于记录最终的最长子序列】，而是【以stk[i]结尾的子串长度最长为i】或者说【长度为i的递增子串中，末尾元素最小的是stk[i]】。理解了这个问题以后就知道为什么新进来的元素要不就在末尾增加，要不就替代第一个大于等于它元素的位置。
这里的【替换】就蕴含了一个贪心的思想，对于同样长度的子串，我当然希望它的末端越小越好，这样以后我也有更多机会拓展。

分析太清晰了，一下就明白了！tql！！！

tql

赞

赞赞赞

牛啊牛啊

%%%

疯狂打call

为什么不能给评论点赞orz

是的，思路瞬间清晰。
个人理解：比如如下数据1 3 6 2 8 9，最长上升子序列明显是1 3 6 8 9 ，但是最终栈中保存的是1 2 6 8 9，同样能求得最长子序列的长度。用的就是一种贪心思想。

懂了，谢谢

对的，大佬这个代码最后不能求出上升的子序列是什么，但是可以在更新前面数据的时候保存一下就是在else这里，虽然最后的子序列不是原序列的子串，但是不影响长度。

巧妙。

看了那么多感觉这个是真把道理讲明白了，可惜不能赞评论hh

牛的

这样以后我也有更多机会拓展。

tql!!!

tql

终于看懂了，赞！

大佬 nb

我来总结一个点：就是最终栈中的元素可能和最长子序列中的元素是不同的，但是其中包含的元素个数却是相同的。

如果题目要求是输出最长子序列，那么这个解法就有问题了，所以适用性不是很强

为什么栈中元素不是最长子序列？有什么说法吗。不过最长子序列也不一定唯一，如果有题目要输出所有最长子序列，那也只好换一种做法了。但这个做法解决这道题应该来说没问题吧

这个不是答案惟不唯一的问题
我来举了例子：1 2 6 8 5
根据栈做法得到的最长子序列应该是 1 2 5 8
但实际答案确实1 2 6 8
但是这道题求的是最大元素个数，所以这个个数是没有问题的。

woc，原来如此%%%

%%%%

这种方法有一点理解难度，先用一个例子进行模拟：

$a=[3,1,4,1,5,9,2]$

循环过程中 $v$ 的变化：

1. $v=[3]$
2. $v=[1]$
3. $v=[1,4]$
4. $v=[1,4]$
5. $v=[1,5]$
6. $v=[1,5,9]$
7. $v=[1,2,9]$

最终，$v$ 的长度为 $3$ 即最长上升子序列长度。

我们会发现一些奇怪之处：

• 这个单调栈的去尾操作并不典型，$6\sim7$ 步时，数字 $9$ 没有被去除而是保留下来了。
• 单调栈的序列并不是最长上升子序列，该例应该为 $[1,5,9]$ 而不是 $[1,2,9]$

首先解决第一个问题，为什么用这种特殊的去尾操作？

原因是贪心，我们要求的是最长的上升子序列，当然不愿意越算子序列长度反而越小了。因此，如果我们目前算出的结果还没以前的长，会暂时保留以前的结果，当然也不丢弃目前的结果，因为之后继续计算的话，目前的结果可能更优。

为了实现上述目的，我们可以用新序列从左到右逐渐覆盖掉旧序列。当新序列长度 $<$ 原序列长度时，原序列没有被完全覆盖，因此保证长度不减小；当新序列长度 $\geq$ 原序列长度时，原序列已经被完全覆盖，现在就是以新序列为基础进行计算了。

因此就产生了这种特别的去尾方式。上述例子的第 $7$ 步可以表示成：
$$ \begin{align} 之前的更好的序列:v=&[1,5,9]\\ 现在的新序列:v=&[1,2]\\ 覆盖储存:v=&[1,2,9] \end{align} $$

第一个问题解决后，第二个问题其实就比较容易了，因为栈中储存的不只有一个序列，是以前的序列和现在的序列合并的产物，因此不一定是最终最长上升子序列。

但是对于长度，由于我们的贪心思想，我们循环过程中栈的长度不减，因此能够保证最长上升子序列的长度就是栈的长度。

茅塞顿开！谢谢大佬！

茅厕顿开！谢谢大佬！

这个例子的最长子序列不应该是1 4 5 9 吗？

订正
1. $v=[3]$
2. $v=[1]$
3. $v=[1,4]$
4. $v=[1,4]$
5. $v=[1,4,5]$
6. $v=[1,4,5,9]$
7. $v=[1,2,5,9]$

###栈中储存的不只有一个序列，是以前的序列和现在的序列合并的产物，因此不一定是最终最长上升子序列。
这句话太关键了

有啥区别吗？和y总的思路一摸一样的代码，一个用了STL一个没用而已

贬低别人并不能抬高自己

你6

要这么玻璃心吗，哪里看出来贬低别人了，再说了，谁配贬低y总？

这也没有贬低吧。。。

还是不太一样，y总用的是upperbound，但是真心建议手写二分

手写二分不太好理解o(╥﹏╥)o

赞同，思路确实一样，不过实现所使用的工具不同，并没有贬低的意思，都很棒

我贬低称冯了个福孩子

孩子，消息了

1 3 4 2 7 5 6 8

1- 3 -4 -》 1 - 2 - 4 - 》1- 2 - 4 - 7-》1-2-4- 5-》1-2-4-5-6 -》 1- 2- 4 -5 -6 -8
实际上的最大上升子序列是1 3 4 5 6 8
但是并不影响 这样做 如果 以 2 结尾的新的子序列比 3结尾的更长就会被替换掉

K神！！！

牛逼，看到这里茅塞顿开

例子：
1 9 10 11 12 2 3 4 5 6 7
得到：
st: 1
st: 1 9
st: 1 9 10
st: 1 9 10 11
st: 1 9 10 11 12
st: 1 2 10 11 12
st: 1 2 3 11 12
st: 1 2 3 4 12
st: 1 2 3 4 5
st: 1 2 3 4 5 6
st: 1 2 3 4 5 6 7

st中保存的是以st[i]为结尾的最长子序列的长度，只需要保证长度最长，不需要保证序列稳定。
新进来的元素要不就在末尾增加，要不就替换掉第一个大于等于他的元素。

替换第一个大于大于他的数的目的是：为了给未来做到更长铺好路。
如果是替换操作：说明我在保持以我为结尾的最长子序列不变的同时，可以让未来能够变得更长！
如果是加在末尾：说明以我为结尾，能够让最长的长度加1了！
上述的例子，从2开始就进行不断的替换，显然，到了6这个地方，就不再是替换了，而是增加了长度！这就是前面的2~5的替换，为6和7的到来铺好了路。

牛逼

我靠我靠我靠 我想复杂了 看y总的课也没你代码给的思路简洁

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int a[N],n;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%d",&a[i]);

    vector<int> f;
    for(int i=0;i<n;++i){
        auto pos=lower_bound(f.begin(),f.end(),a[i]);
        if(pos!=f.end())*pos=a[i];
        else f.push_back(a[i]);
    }
    cout<<f.size()<<endl;
    return 0;
}

dalao这个写法好简洁%%%

$巨巨巨$！！

我也感觉用 vector就行了，不必用stack

是不是可以这样理解，所有的栈不是为了求出具体的值，只是为了看这个栈到底能延伸到哪里，就是说前面的数据都是为了维护结尾而诞生。要有长度为4的队列，我们希望长度为3的队列最后的末尾越小越好，这样留给4的空间相对更大。

可以理解为，他每次替换元素都是，增加了序列长度增长的潜力

顿悟了ohhhh！！

为什么用upper_bound()不行

数列严格递增，输入123后再输入两次1，用upper_bound()会修改为111，只能维持单调不减

太感谢了，upper一直t，后来才发现不能将刚好够的后面一个给改了，要不然就不严格了

y总这个代码是左闭右开的，但是在二分算法里面的模板都是左闭右闭，因此很让人困惑，因为我只想用那两个模板，经过一个多小时的钻研，我给出左闭右闭的代码，如果对你有帮助，请点赞评论，让我知道我的努力是有意义的。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010; // 定义数组的最大长度

int n;      // 用于存储输入序列的长度
int a[N];   // 输入序列
int q[N];   // 维护的最长递增子序列

int main()
{
    cin >> n; // 读取序列的长度
    for(int i = 0; i < n; i++) cin >> a[i]; // 循环读取序列的每个元素

    int len = 1; // 初始化最长递增子序列的长度为1
    q[0] = a[0]; // 将输入序列的第一个元素作为最长递增子序列的起始元素

    // 从输入序列的第二个元素开始遍历
    for(int i = 1; i < n; i++){
        int l = 0, r = len - 1; // 设置二分查找的范围，[l,r]表示q数组的有效范围

        // 使用二分查找，在q中找到第一个大于等于a[i]的元素的位置
        while(l < r){
            int mid = (l + r) / 2; // 计算中间位置
            if(q[mid] < a[i]) l = mid + 1; // 如果中间位置的元素小于a[i]，搜索右半边
            else r = mid; // 否则搜索左半边
        }

        // 判断找到的位置l和最长递增子序列的末尾元素的关系
        if(l == len - 1 && q[l] < a[i]){ // 如果l指向最长递增子序列的末尾且a[i]可以扩展这个序列
            q[l + 1] = a[i]; // 将a[i]添加到q的末尾
            len++; // 更新最长递增子序列的长度
        }else{
            q[l] = a[i]; // 如果a[i]不扩展最长递增子序列，则用它更新q[l]的值
        }
    }

    cout << len << endl; // 输出最长递增子序列的长度
    return 0;
}

1. 这个算法最关键的点在于，栈维护的是长度为 i 的子序列的最后一个元素的最小值。这一点很好理解，因为我们每遇到一个比栈尾元素小的新元素时，就会用它更新栈中第一个不小于该元素的元素。
2. 其次由于我们对于新的元素只有两种处理方式：加入或者替换，这就保证了一定能找到最长的子序列，但是不能保证可以找到最长子序列的具体元素。

对于所有的新的元素有两种状态，第一：比所有的元素都大，那么它应当作为一个新的长度目前的最小值存入栈中。第二：有比它大的值存在，那么它存在的意义就是基于贪心，替换掉第一个比它大的值，这样就能位置栈的单调递增的效果。

卧槽，太牛了，而且相当容易思考

你能解释一下为什么这是合理的吗

我的建议是你按照这个程序手动模拟一下这个过程，就会很清晰了

你再仔细想想，stk栈里面维护的不是最长的序列，但是stk里面的元素个数维护的是最长序列的长度，这种贪心思维是需要数学证明的，模拟我早几个月就模拟出来了

我同意贪心思维是需要数学证明的，但是题目中的最长上升子序列可能并不唯一，stk中只提供了一种解法，比如3，5，4的最长上升子序列可以是3-5，3-4，题目中stk存的应该是3-4，确实能求出答案，但只是一种方案

如果当前值大于栈尾则用当前值扩大子序列长度
反之则看看是否能利用当前值构造新的子序列使长度大于原来最长子序列
核心思想：最长子序列的长度的增长只与栈尾有关
栈中元素具体为什么值并不影响子序列的长度

老哥解释得很清晰

bushide

大佬太强了

已踩

为啥啊

的反义词

// lower_bound 在头文件 algorithm 里面，返回类型是迭代器(类似于指针一样的东西)。
// 返回一个容器里面的第一个小于等于 value 的值的迭代器
// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

  return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    // 先放一个值进去
    vector<int> v;
    int x;
    cin >> x;
    v.push_back(x);

    // 再放剩下的 n - 1 个值进去
    for(int i = 1; i < n; i++){
        cin >> x;

        // 直接判断
        if(x > v.back()) v.push_back(x);
        else *lower_bound(v.begin(), v.end(), x) = x;
    }

    cout << v.size() << endl;

    return 0;
}

*lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
为啥不加*会报错啊

lower_bound返回的是指针 前面加*就是取那个值 然后再赋值~

这个举例非常清晰

orz

太NB了吧佬，ORZ

orz