Uber 电面

求米看帖！会继续更新下一轮面经！

Given an array of envelopes, find the longest sequence such that you are able to fit a envelope inside another for all envelopes in that sequence.
The envelopes

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

20,20}, {3,8}, {6,1}, {7, 2}, {1,1}, {3,4}, {20,20} }
Return: { {10,10}, {9,9}, {3,8}, {7,2}, {1,1} }

感谢楼主分享！

要求O（N）完成嗎？

我只想到了N^2的DP算法，你有线性算法吗？

是不是先要对每个元素排序，因为可以rotate，把高度或宽度小的放前面，大的放后面，然后再把所有envelope排序，然后套用dp大法

zhqfox 发表于 2019-5-22 08:31
是不是先要对每个元素排序，因为可以rotate，把高度或宽度小的放前面，大的放后面，然后再把所有envelope排 ...

题目说的是 subsequence. 排序之后怎么保证顺序是对的。

kevindx1120 发表于 2019-5-25 13:48
题目说的是 subsequence. 排序之后怎么保证顺序是对的。

subsequence, 那就只能直接上dp， 不排序了。