 # 61. 寻找天际线

RT

Scala 版：

``````  final case class Rect(left: Int, right: Int, high: Int)

def skylinePointsMaxHeap(bindings: Vector[Rect]): Vector[(Int, Int)] = {
var result: Vector[(Int, Int)] = Vector()
val height: Vector[(Int, Int)] = bindings
.flatMap { arr =>
(arr.left, -arr.high) :: (arr.right, arr.high) :: Nil
}
.sortWith { case ((aX, aH), (bX, bH)) => if (aX == bX) aH < bH else aX < bX }

var pq = mutable.PriorityQueue[Int](0) // Maximum in queue header.
var preHeight = 0
for ((x, h) <- height) {
if (h < 0) pq.enqueue(-h)
else pq = pq.filterNot(_ == h)

}
}

result
}

def skylinePointsTreeMap(bindings: Vector[Rect]): Vector[(Int, Int)] = {
var result: Vector[(Int, Int)] = Vector()
val height: Vector[(Int, Int)] = bindings
.flatMap { arr =>
(arr.left, -arr.high) :: (arr.right, arr.high) :: Nil
}
.sortWith { case ((aX, aH), (bX, bH)) => if (aX == bX) aH < bH else aX < bX }

val tree = mutable.TreeMap[Int, Int](0 -> 1)
var preHeight = 0
for ((x, h) <- height) {
if (h < 0) {
tree.updateWith(-h) {
case Some(n) => Some(n + 1)
case None    => Some(1)
}
} else {
tree.updateWith(h) {
case Some(1) => None
case Some(n) => Some(n - 1)
case None    => None
}
}

val max = tree.lastKey
if (max != preHeight) {
preHeight = max
result :+= x -> max
}
}

result
}
``````

``````class P061SkylineTest extends AnyWordSpec with Matchers {
import P061Skyline._

private val data1 = Vector(Rect(1, 3, 2), Rect(2, 4, 3), Rect(5, 9, 2), Rect(6, 8, 4))
private val result1 = Vector((1, 2), (2, 3), (4, 0), (5, 2), (6, 4), (8, 2), (9, 0))
private val data2 = Vector(Rect(2, 4, 2), Rect(2, 4, 3), Rect(5, 7, 2), Rect(7, 9, 4))
private val result2 = Vector((2, 3), (4, 0), (5, 2), (7, 4), (9, 0))

"MaxHeap" should {
"X axis does not coincide" in {
skylinePointsMaxHeap(data1) shouldBe result1
}

"X axis coincidence" in {
skylinePointsMaxHeap(data2) shouldBe result2
}
}

"TreeMap" should {
"X axis does not coincide" in {
skylinePointsTreeMap(data1) shouldBe result1
}

"X axis coincidence" in {
skylinePointsTreeMap(data2) shouldBe result2
}
}
}
``````