骨骼新鲜店面

感觉就是模拟啊，最直观的思路开个长度为w的array纪录每个点的高度，落下新矩阵的时候扫一遍看哪里放最矮

我觉得这道题的难点在于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]

感觉我们需要 记录三个值, <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.....

求问楼主timeline？多谢！

请问楼主投的是哪个岗位呀

能问一下楼主思路吗？

完全没有思路啊。。。

是不是可以考虑把已经存在的矩形按顺序存成(x, y)的事件点，然后对每个新矩形，做宽度为width的滑动窗口，把覆盖到的事件点维护在一个queue里，queue里最高点决定了当前矩形位置，全部滑动完之后就找到最小值了。

PG0321 发表于 2020-8-20 12:37
是不是可以考虑把已经存在的矩形按顺序存成(x, y)的事件点，然后对每个新矩形，做宽度为width的滑动窗口， ...

请问能举个例子嘛？感觉没太看懂这个思路。

感觉这道题是hard啊。当考虑最佳落点的时候，可以不考虑后续的图形这句话好像暗示是dp。但是实际考虑这个问题又好像是一个高度dfs。lc好像有类似的原题。最后我还感觉是segment tree捂脸

感觉是segment tree + sliding window 的结合啊 hard 必定了