骨骼新鲜店面

完全没找到投递链接啊

请问🐶家2021 new grad开了？能发一下链接么？完全没找到 谢谢

泡利不相容 发表于 2020-8-21 04:55
感觉就是模拟啊，最直观的思路开个长度为w的array纪录每个点的高度，落下新矩阵的时候扫一遍看哪里放最矮

感觉是这个思路

二分查找。

感觉可以用treemap来解决
1 先把[1, 0] -> [w, 0] 存在treemap里，然后按照每个点最低的排序
2 然后每个方块来的时候，loop 这个treemap，然后找到连续的可以放下这个方块的最低点，然后放入方块更新treepmap
3然后找出treemap最大的点？

感觉我们需要 记录三个值, <height, start index, length>

放进一个pq, 每次从最小height, 最小start index 开始, 找到 length 满足条件的, split 这个状态, (但是之前找出来的, 不满足条件的, 还得放回pq里面去🤣)

<height+矩形高度, startindex, 矩形宽度> 和 <height, startindex+矩形宽度, length-矩形宽度> 然后再放回pq里面, 在这个过程中maintain最大高度

这个复杂度是 nlog(n) ?

这么弄, 感觉就是用了pq优化了brute force 解, 不用每次花O(n)去找该在哪插入, 以及更新range.

不知道这样对不对, 坐等大佬给出 segment tree 之类的解法.




补充内容 (2020-8-26 00:55):
pls ignore, i am too naive

得用个别的数据结构, 这个还会影响 下一个 range.....

谢谢楼主分享
请问放置每个矩形的时候要考虑旋转吗？比如转九十度就是width, height互换

我觉得这道题的难点在于corner case。首先要clarify几种情况，比如说，矩形是直接落下还是可以中途变道。如果可以变道，比如说你某些地方会分层，玩过俄罗斯方块的都知道我什么意思吧，贴着空隙进去，然后再往里面硬塞，这样的话每一个W点对于不同大小的方块其实可能是不同的高度，空隙够你进去，你就可以认为取较小的高度，进不去就要用顶上的高度。mock倒是可以mock，复杂度就会很高了。暂时想不出来特别优的解法。另外，找出最低点没办法用pq，因为最低点不一定放的进去，比如一个凹口。所以实际上是一个连续的array，找到一个矩阵长度的连续array，最大值最小。这就是另外一个hard难度的题了，sliding window找到所有的最大/最小值。时间复杂度是O(n)。这道题就是O(W), 下面附上代码。算了一下从看题到先用pq尝试失败，再到sliding window，再到写出代码差不多是20分钟，不过这个不需要沟通，现实面试通常也就40分钟不到，大概率我也没办法写出来，还有紧张的因素，以及你不太方便尝试将不说话闷头做测试。哎，看不到面经大概率也是挂。

1. public class Solution {
   
2.     public int findHighestPoint (int[][] rectangles, int W) {
   
3.         int[] base = new int[W];
   
4.         for (int[] rectangle : rectangles) {
   
5.             int index = findIndex(W, rectangle[0]);
   
6.             for (int i = index; i < rectangle[0] + index; i++) {
   
7.                 W[i] += rectangle[1];
   
8.            }
   
9.         }
   
10.         int max = 0;
    
11.         for (int value : W) {
    
12.             max = Math.max(max, value);
    
13.        }
    
14.        return max;
    
15.     }
    
16. 
    
17. private int findIndex (int[] W, int k) {
    
18.     int height = Integer.MAX_VALUE, index = 0;
    
19.    Deque<Integer> deque = new ArrayDeque<>();
    
20.    for (int i = 0; i < W.length; i++) {
    
21.        if (i >= k) {
    
22.            if (deque.peekFirst() == (i - k)) {
    
23.                deque.pollFirst();
    
24.           }
    
25.       }
    
26.      while (!deque.isEmpty() && W[deque.peekLast()] < W[i]) {
    
27.            deque.pollLast();
    
28.       }
    
29.      while (!deque.isEmpty() && W[deque.peekFirst()] < W[i]) {
    
30.            deque.pollFirst();
    
31.      }
    
32.     deque.offerLast(i);
    
33.     if (i - 1 >= k) {
    
34.           if (W[deque.peekFirst() < height) {
    
35.                 index = i - 1 - k;
    
36.                 height = W[deque.peekFirst()];
    
37.          }
    
38.       }
    
39.    }
    
40.     return index;
    
41.    }
    
42. }
    

复制代码

[/i][/i][/i]

这题思路可以参考下 利口 依儿肆零  

需要用暴力dfs() 屏幕的宽度w 不能太大  因为每层dfs()都要深度复制一遍屏幕

暴力遍历 每次方块落下试着从最左边开始放方块 把横着落下还是竖着插入都dfs()一遍 每次都计算下结果