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)

      if (pq.head != preHeight) {
        preHeight = pq.head
        result :+= x -> pq.head
      }
    }

    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
    }
  }
}