求小红书笔试最后一题python代码或者思路

leetcode354

用最长上升子序列的nlogn解法。

from functools import cmp_to_key class Solution(object):     def maxEnvelopes(self, envs):         def liss(envs):             def lmip(envs, tails, k):                 b, e = 0, len(tails) - 1                 while b <= e:                     m = (b + e) >> 1                     if envs[tails[m]][1] > k[1]:                         e = m - 1                     else:                         b = m + 1                 return b             tails = []             for i, env in enumerate(envs):                 idx = lmip(envs, tails, env)                 if idx >= len(tails):                     tails.append(i)                 else:                     tails[idx] = i             return len(tails)         def f(x, y):             return -1 if (x[0] < y[0] or x[0] == y[0] and x[1] > y[1]) else 1         envs.sort(key=cmp_to_key(f))         return liss(envs) if __name__ == "__main__":     N = int(input())     block = []     for _ in range(N):         tmp = list(map(int, input().split()))         block.append(tmp)     print(Solution().maxEnvelopes(block))

# 没测试对不对，写的时候把l1写成l2了，没发现。。。 N = int(raw_input()) li = [] for _ in range(N):     li.append([int(i) for i in raw_input().split()]) def helper(l1, l2):     m1, m2 = max(l1), max(l2)     if m1 < m2:         return -1     elif m1 > m2:         return 1     m1, m2 = min(l1), min(l2)     if m1 > m2:         return 1     elif m1 == m2:         return 0     return -1 li.sort(cmp=helper) res = 1 for i in range(1, len(li)):     if li[i][0] >= li[i-1][0] and li[i][1] >= li[i-1][1]:         res += 1 print(res)

n = int(input()) baowu = [] for i in range(n):     baowu.append(list(map(int,input().split()))) def maxEnvelopes1(baowu):     '''     动态+二分查找     :param envelopes:     :return:     '''     baowu.sort(key=lambda x: (x[0], -x[1]))     nums = []     for i in baowu:         nums.append(i[1])     stack = [0] * len(nums)     maxl = 0     for x in nums:         low, high = 0, maxl         while low < high:             mid = low +(high - low) // 2             # 只要改这一行代码即可             if stack[mid] <= x:                 low = mid + 1             else:                 high = mid         stack[low] = x         maxl = max(low + 1, maxl)     return maxl print(maxEnvelopes1(baowu)) leetcode 354  只要改一行代码

是求最长递增子序列吗？算法时间复杂度可以改进