从俯视图可见的堆栈
这是一个面试问题。
以下是按如下方式排列的注释，如图所示。给定每个音符的起点和结束点。
例如。2-5，3-9，7-100在长度限制0-10^9的范围内，在这个例子中，所有三个音符都是可见的。
我们需要找出，当从顶部查看时，有多少注释是可见的？
我尝试在O(n*n)中求解，其中n是通过检查每个音符与其他音符的可见性来计算音符的数量。但是在这种方法中，我们将如何确定这两个注释是否在不同的堆栈中。最终没有达成解决方案。
O(n)解将被优先考虑，因为面试官要求O(n)解
回答 2
Stack Overflow用户
发布于 2014-10-06 16:00:55
如果O( among )足够:首先，将输入中的所有数字重新映射为介于0..(2*n+1)之间(即，如果某个数字x_i是输入中所有数字中的第j个最小数字，则将所有x_i替换为j)。然后，您可以在分段树上使用Painter算法。
详细信息：
考虑一个大小为(2 *n+ 1)的数组。用-1初始化所有这些单元格。
画家的算法:从最后一张纸币(在底部)到最上面的纸币进行迭代。对于覆盖从a_i到b_i的每个注释，将数组中索引在a_i和b_i之间的所有单元格的值替换为i。在此算法结束时，我们可以简单地查看数组中有哪些索引，这些索引构成了所有可见的注释。然而，这在O(N^2)中很天真地工作。
段树:因此，我们不使用数组，而是使用段树。然后，上述操作可以在O(log )内完成。
Stack Overflow用户
发布于 2014-10-06 17:06:36
如果输入中注释的顺序是“前者在顶部”，那么它很简单：
保留min_x和max_x的值，将其初始化为第一个音符的x值。遍历注释，每个具有大于max_x或小于min_x的x值的注释将这些相应的值更改为其自己的x值，并被视为可见，否则不可见。完成迭代并返回可见注释的列表。把钱收起来。
https://stackoverflow.com/questions/26211727
复制相似问题
腾讯云开发者
