推箱子
5. 一个洞穴里面很多格，每一格都是不同的高度，还有一堆object, 每个的高度不同，问这个洞穴最多可以放多少个object，往洞穴放object的话要注意是从洞口往里放，所以靠近洞口的格子的高度会限制后面的高度，因为object会被卡住。。. 每个格子只能放一个object，object不能叠加。
第三题：地里的面经题。有一个山洞，可以看作一维height数组。 另外有一堆箱子boxes， 要求将箱子从外面推到山洞里面，问最多能推多少箱子进山洞。楼主先解释了为什么要先将箱子高度排序，先推矮箱子，再推高箱子。同时山洞的每一个位置i都最多能容许min(heights[:i])的箱子通过。 根据这点建立一个allowedHeight数组，可以看出是单调不增的序列， 因此对每个箱子高度可以bisect寻找allowedHeight里面对应的position index. 讨论了时间复杂度 O(log(len(height))*len(boxes))。电脑写了code后和面试小哥讨论了几点可以优化的地方，最后小哥表示时间复杂度还可以优化，在提示下使用two pointer方法，让两个pointer分别指向最矮箱子的position和最小allowedHeight position, 依次比较二者的大小来分别递增两pointer。 时间复杂度可以变成O(len(height)+len(boxes))
我来描述一下吧：
假设山洞有三个格子，从左到右（也是从最深到洞口的顺序）的高度分别是: 5, 10, 6 【洞口】。见下图：
那么可知最左的格子最多只能放5，中间的格子只能放6，因为6以上的箱子无法从洞口通过最右边的只有高度6的格子，也就不可能到中间。最右边的格子最多只能放6。因此箱子进洞有着单调性。另外格子里最多可以放一个箱子。
如果我有这些箱子：📦 10, 30, 6, 5, 8，7，那么在排序以后，我 应该 5 放最左，6放中间或者左边。有一个格子空着。7,8,10,30这些箱子不能放入。
https://www.1point3acres.com/bbs ... read&tid=511673
https://www.1point3acres.com/bbs ... read&tid=444025
5. 一个洞穴里面很多格，每一格都是不同的高度，还有一堆object, 每个的高度不同，问这个洞穴最多可以放多少个object，往洞穴放object的话要注意是从洞口往里放，所以靠近洞口的格子的高度会限制后面的高度，因为object会被卡住。。. 每个格子只能放一个object，object不能叠加。
第三题：地里的面经题。有一个山洞，可以看作一维height数组。 另外有一堆箱子boxes， 要求将箱子从外面推到山洞里面，问最多能推多少箱子进山洞。楼主先解释了为什么要先将箱子高度排序，先推矮箱子，再推高箱子。同时山洞的每一个位置i都最多能容许min(heights[:i])的箱子通过。 根据这点建立一个allowedHeight数组，可以看出是单调不增的序列， 因此对每个箱子高度可以bisect寻找allowedHeight里面对应的position index. 讨论了时间复杂度 O(log(len(height))*len(boxes))。电脑写了code后和面试小哥讨论了几点可以优化的地方，最后小哥表示时间复杂度还可以优化，在提示下使用two pointer方法，让两个pointer分别指向最矮箱子的position和最小allowedHeight position, 依次比较二者的大小来分别递增两pointer。 时间复杂度可以变成O(len(height)+len(boxes))
我来描述一下吧：
假设山洞有三个格子，从左到右（也是从最深到洞口的顺序）的高度分别是: 5, 10, 6 【洞口】。见下图：
[Bash shell] 纯文本查看 复制代码
------ | |------|-----| ||____________________ 洞口 高度5 高度10 高度6 |
那么可知最左的格子最多只能放5，中间的格子只能放6，因为6以上的箱子无法从洞口通过最右边的只有高度6的格子，也就不可能到中间。最右边的格子最多只能放6。因此箱子进洞有着单调性。另外格子里最多可以放一个箱子。
如果我有这些箱子：📦 10, 30, 6, 5, 8，7，那么在排序以后，我 应该 5 放最左，6放中间或者左边。有一个格子空着。7,8,10,30这些箱子不能放入。
https://www.1point3acres.com/bbs ... read&tid=511673
https://www.1point3acres.com/bbs ... read&tid=444025
洞O[n] 做递减数组
箱子排序, 挨个match.
