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]] >= k: 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 < y or x == y and x > y) else 1 envs.sort(cmp=f) return liss(envs) # Runtime: 100ms
The idea is to order the envelopes and then calculate the longest increasing subsequence (LISS). We first sort the envelopes by width, and we also make sure that when the width is the same, the envelope with greater height comes first. Why? This makes sure that when we calculate the LISS, we don't have a case such as [3, 4] [3, 5] (we could increase the LISS but this would be wrong as the width is the same. It can't happen when [3, 5] comes first in the ordering).
We could calculate the LISS using the standard DP algorithm (quadratic runtime), but we can just use the tails array method with a twist: we store the index of the tail, and we do leftmost insertion point as usual to find the right index in
nlogn time. Why not rightmost? Think about the case [1, 1], [1, 1], [1, 1].
@agave I hope every programmer in this world could explain their thought as clear as you did.
@agave i guess you could also have written
envelopes.sort(key=lambda x: (x, x))
Is the same, just using lambda and in one line :)
BTW. just loved your right shift instead of dividing by 2 :D Really sweat
Shorter version using bisect
import bisect class Solution(object): def maxEnvelopes(self, envelopes): """ :type envelopes: List[List[int]] :rtype: int """ if not envelopes: return 0 envelopes.sort(key=lambda x:(x,-x)) h= for i,e in enumerate(envelopes,0): j=bisect.bisect_left(h,e) if j<len(h): h[j]=e else: h.append(e) return len(h)
Hey can you please explain what you're doing or what is an algorithm captured in
h= for i,e in enumerate(envelopes,0): j=bisect.bisect_left(h,e) if j<len(h): h[j]=e <---- what does it do?? else: h.append(e)
e is the height of the current envelop. h stores the heights of the envelopes before current envelop. And because envelopes are sorted by (width, -height), so current envelop's width is equal or larger than the envelopes before it. h[j] = e is trying to put current envelop in the right place.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.