j**l
发帖数: 2911 | 1 Given a list of boxes with known dimension, you can stack a box onto another
if it has smaller width and length. Find highest stack you can make.
感觉这和Careercup那个马戏团叠罗汉题有点像，那道题可以按体重或身高排序，再用
数组最长递增子序列(LIS)来做 |
y*c
发帖数: 904 | |
z****e
发帖数: 2024 | 3 请问有没有LIS的 code？自己写了一个，不好,要O(n^2). |
j**l
发帖数: 2911 | 4 Wiki上有O(nlgn)的，方法很巧，主要是要用到二分查找来加速，关键是维护一个数组A
，A[i]保存的是长度为i的递增序列的末尾元素的最小值.
面试官估计很难相信是你当场想出来的。
【在 z****e 的大作中提到】
: 请问有没有LIS的 code？自己写了一个，不好,要O(n^2).
|
w****m
发帖数: 146 | |
z****e
发帖数: 2024 | |
w****m
发帖数: 146 | 7 不是我写的。。。
【在 z****e 的大作中提到】
: 你写的？太牛了。
|
