按照所述方法排序之后，只要计算出（按h的）最长递降子序列的长度k，就是最终结果。首先易证，不可能比k更小，因为这k个娃娃中任意两个都套不住彼此，所以至少要k套娃娃才行；其次证明，可以找到一种套法，可以用k套娃娃包含所有。方法是，从第一个开始，套的上就套，套不上就先放拿，试下一个；一趟套完之后套上的都拿走，再套下一趟，直到全套完。证明这种套法k次肯定能全套完：反证，假设套不完，那么第k次套完之后假设还剩下个h0，那么在套地k次之前，在h0位置的前面肯定存在一个h1比h0要大，否则h0前面的如果全比h0小，那么套到h0的时候就肯定给套走了；以此类推，在套k-1次之前，肯定在h1前面有个h2比h1大。。。于是，在套第1次之前，肯定有hk>hk-1...>h2>h1>h0，那么这是长度为k+1的递降子序列，矛盾。
然后，找最长单调子序列的时间复杂度有O(n)吧我记得。