目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明:
不允许旋转信封。

示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3 
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

二、解题思路

先对信封按照宽度w升序排序，然后再对相同宽度w的信封按照高度h降序；

高度降序的目的是在对排好序的信封数组里，用一个数组存储高度h，并利用二分插入方式存储信封的高度h（LIS：最长上升（不下降）子序列）；

如果信封的宽度w一样，则选择高度h小的，否则就会存放相同宽度w的不同高度h的信封，但是宽度w是不能一样的，因此之后要按照高度h降序，这样就可以更新这个高度h。

三、代码

  

   

    

     

    
    

     

      from bisect import bisect_left
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def LIS(self, nums):
     
    
   

    

     

    
    

     

       res = []
     
    
   

    

     

    
    

     
 for num in nums:
     
    
   

    

     

    
    

     

       index = bisect_left(res, num)
     
    
   

    

     

    
    

     
 if index == len(res):
     
    
   

    

     

    
    

     

       res.append(num)
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       res[index] = num
     
    
   

    

     

    
    

     
 return len(res)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def maxEnvelopes(self, envelopes: list) -> int:
     
    
   

    

     

    
    

     

       envelopes.sort(key=lambda x: (x[0], -x[1]))
     
    
   

    

     

    
    

     

       print(envelopes)
     
    
   

    

     

    
    

     
 return self.LIS([envelope[1] for envelope in envelopes])
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       envelopes = [[4, 5], [4, 6], [6, 7], [2, 3], [1, 1]]
     
    
   

    

     

    
    

     

       ans = s.maxEnvelopes(envelopes)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/114361844