搭积木
题目描述解题思路1. 寻找最大非递减子集1. O( N 2 N^2 N2)2. O(nlogn) 2. 解题方法补充知识点lower_bound & upper_bound题目描述
小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？
定义每一个长方形的长L和宽W都为正整数，并且1 <= W <= L <= INT_MAX, 袋子里面长方形的个数为N, 并且 1 <= N <= 1000000.
假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。
解题思路
先对宽排序
那么问题就转化成：寻找此时所有长的最长不递减子序列
<
如果觉得《校招真题编程（十八）搭积木》对你有帮助，请点赞、收藏，并留下你的观点哦！
