脸熟店面求加米

亚特兰蒂斯 发表于 2019-6-3 11:29
正解。单调栈。贴个代码：
        Stack stack = new Stack();                int i = 0;

不知道原题问的“能看到海的下标”，是指只要这个楼房有能看到海的房间，就算true了吗？

那 @亚特兰蒂斯 2 这个解还是有问题的。
第i+1的房子，可能比前面的矮，但是如果比前面的都宽，也是能看到海的
你这里只考虑高度，没考虑宽度





补充内容 (2020-10-2 12:41):
我理解错了，以为楼房是(x1, x2, hight)
原来这题只是给楼房高度的数组，那就从右向左扫描即可。记录当前的最大值。比这个小的就看不到，不这个大的就能看到，同时更新最大值，

Optimus 发表于 2019-5-31 07:25
谢楼主分享。第一题leetcode上也有，skyline problem。祝楼主顺利。

跟skyline也不同

skyline的楼房没有数组顺序的先后关系，所以可以排序后，然后在x轴上从小到大用类似求overlap的算法。
这里有先后关系吧。先输的楼房在前面，即便很窄很矮，也是能看到海的。

感觉就是从左到右扫描，维护一个skyline那样的阴影（多边形）面积。新进来一个数组，看有没有完全被这个阴影挡住。完全挡住就忽略，否则加入list, 并更正skyline.
但skyline的求法，应该比利口的简单，因为前i个楼已经算过了，只要算i+1加进去后什么样。

attar 发表于 2020-9-28 13:05
跟skyline也不同

skyline的楼房没有数组顺序的先后关系，所以可以排序后，然后在x轴上从小到大用类似 ...

我理解错了，以为楼房是(x1, x2, hight)。 =》skyline的变型，但不完全是。这个就比较难。

这题只是给楼房高度的数组，那就从右向左扫描即可。记录当前的最大值。比这个小的就看不到，不这个大的就能看到，同时更新最大值。这个是easy难度