10 lines Python code beats %96.


  • 4
    G
    class Solution(object):
        def maxEnvelopes(self, envelopes):
            des_ht = [a[1] for a in sorted(envelopes, key = lambda x: (x[0], -x[1]))]
            dp, l = [0] * len(des_ht), 0
            for x in des_ht:
                i = bisect.bisect_left(dp, x, 0, l)
                dp[i] = x
                if i == l:
                    l+=1
            return l
    

  • 0
    8

    @geeti

    class Solution(object):
        def maxEnvelopes(self, envelopes):
            r = []
            for env in sorted(envelopes, key=lambda x: (x[0], -x[1])):
                pos = bisect.bisect_left(r, env[1])
                if pos==len(r):
                    r.append(env[1])
                elif env[1]<r[pos]:
                    r[pos] = env[1]
            return len(r)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.