題目：給定一個N行2列的二維數組，每一個小數組的兩個值分別代表一個信封的長和寬。如果信封A 的長度都小于信封B，那么信封A可以放在信封B里，請返回信封最多嵌套多少層

舉例：

matrix = [[3,4],[2,3],[4,5],[1,3],[2,2],[3,6],[1,2],[3,2],[2,4]]

信封最多可以套4層，從里到外分別是[1,2],[2,3],[3,4],[4,5],所以返回4

時間復雜度為O(NlogN)

?思路：數組長度從小到達排序，長度相等的信封寬度按照從大到小排序

長度排序之后，可以忽略長度，只看寬度數組，問題轉化為寬度數組的最長遞增子序列問題

＃ encoding = 'utf-8'import numpy as npmatrix = [[3,4],[2,3],[4,5],[1,3],[2,2],[3,6],[1,2],[3,2],[2,4]] matrix.sort(key=lambda x: (x[0],-x[1])) arr = [] for i in range(len(matrix)):arr.append(matrix[i][1])def getOrderLIS(arr,dp):maxlen = 0index = 0"""找到最大值及索引"""for i in range(len(arr)):if arr[i] > maxlen:maxlen = arr[i]index = ires = [0 for i in range(maxlen)]res[maxlen-1]= arr[index]maxlen -=1"""找到之后，從右向左查找"""for j in range(index,-1):if arr[j] < arr[index] and dp[j] == dp[index] - 1:res[maxlen-1] = arr[j]maxlen -=1index = jreturn resdef getdp2(arr):dp = [0 for i in range(len(arr))]ends = [0 for i in range(len(arr))]right = 0dp[0] = 1ends[0] = arr[0]for i in range(1,len(arr)):l = 0r = rightwhile l <= r:m = (l+r)//2if arr[i] > ends[m]:l = m + 1else:r = m - 1right = max(right,l)dp[i] = l + 1ends[l] = arr[i]return dpdef getlist(arr):if arr == None or len(arr) == 0:return Nonedp = getdp2(arr)return getOrderLIS(arr,dp)getlist(arr)

最長遞增子序列問題可參考：

https://blog.csdn.net/weixin_41362649/article/details/98470219

?

總結

以上是生活随笔為你收集整理的信封嵌套问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。