本文共 360 字，大约阅读时间需要 1 分钟。

每栋楼有左边界L，右边界R，高度H，现在有N栋楼，有可能相互遮挡，问每个坐标最大高度是？

线段树 or 有序表 ？ 时间O(NlogN)

线段树：

初始叶节点为0，非叶节点置为0x1000，一个负数表示未处理，[L,R]边界更新线段树节点最大值。 输出时，线段树求解[0,N-1]，若为负数，则找子节点，直到某个区间找到一个非0的数。

有序表：

所有楼按左边界，右边界拆分成两种记录，(坐标loc，高度H，状态)，其中状态分为，加入 or 删除，所有左节点为加入状态，所有右节点为删除状态。

将所有记录按坐标排序。

从0开始遍历每个坐标，同时，维护另一个有序表，结构为(高度，次数)，表示高度H出现了几次。

然后加入 or 删除 状态就是对这个有序表进行添加或减少。

由于有序表的特性，可以O(1)获得当前坐标最大高度。

转载地址：http://ebwji.baihongyu.com/