https://leetcode.com/problems/russian-doll-envelopes/?tab=Description

包信封问题，可以转化成最长有序子序列问题，见下面的分析：

https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation/2

尤其是其中第二部分C++的解法。

 

而最长有序子序列问题：

https://leetcode.com/problems/longest-increasing-subsequence/?tab=Description

 

非常经典，是可以有O(nlgn)的解法的：

解法在上面那道题目的解法里面也有体现。实现如下：

 

class Solution {public:    static bool cmp_first(const pair
     
      & i, const pair
      
       & j) {        if (i.first == j.first)            return i.second > j.second;        return i.first < j.first;    }    int maxEnvelopes(vector
       
        
         >& envelopes) {        vector
         
           candidates;        sort(envelopes.begin(), envelopes.end(), cmp_first);        vector
          
            dp; for (int i = 0; i < envelopes.size(); ++i) { auto itr = lower_bound(dp.begin(), dp.end(), envelopes[i].second); if (itr == dp.end()) { dp.push_back(envelopes[i].second); } else { *itr = envelopes[i].second; } } return dp.size(); }};
          
         
        
       
      
     

其中用到了 lower_bound，这个函数的含义，找出本身作为lower_bound的位置，也就是第一个大于等于输入数的位置。