Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Hard 218. The Skyline Problem

leetcode
tags: leetcode

今回から解答はC++だけにしようと思います

というのもPythonという言語が好きじゃない(主にポインタ操作が出来ないので挙動が分かりにくい点)からです

C++の方が勉強していて楽しいというのもありますし, 言語仕様をしっかり知っているかで各コードに差が出るので当分C++で書こうかな

問題

街の地平線は遠くから見たときのその街の全ての建物によって出来上がるシルエットの外側の等高線である. では, 都市の景観写真で見えるように全ての建物の場所と高さが与えられたと仮定し, これらの建物全体によって作り上げられる地平線を出力するプログラムを書け.

それぞれの建物の地理的な情報は3組の整数[Li, Ri, Hi]によって表現されて, LiとRiはそれぞれ$i$番目の建物の左右端のx座標であり, Hiはその高さである. $0 \leq \text{Li}, \text{Ri} \leq \text{INT_MAX}, 0 < \text{Hi} \leq \text{INT_MAX}$は保証されている. 全ての建物は高さ$0$の完全に平らな表面の上に接地した完璧な長方形だと仮定して良い.

(例は省略)

出力は[x1, y1], [x2, y2], [x3, y3], ...という地平線を一意に定義する書式の｢重要な点｣のリストである. 重要な点は地平線の断片の左の終端である. 最も右の建物が終わる最後の｢重要な点｣はただ地平線の終わりを印すのに使われているだけであり, いつも高さは$0$である. また, どんな2つの隣り合う建物の間の地面は地平線の等高線の一部であると認識されなければならない.

(例は省略)

注意:

  • そんな入力リストの建物の数も$0$以上$10000$以下だと保証されている

  • 入力のリストは既に左のx座標で降順に整列されている

  • 出力リストはx座標で整列されていなければならない

  • 出力の地平線に連続した等しい高さの地平線があってはならない(例は省略)

解法

問題文が長い...

要はいくつかの建物のシルエットがどうなっているかを答えれば良いわけですね

ここではstd::multisetを使って解きます. これはstd::setの重複可能版みたいなデータ構造です. 木構造で要素を管理するので参照が$O(\log n)$で可能です(要素数が$n$のとき). std::mulltisetは内部でソートされている(木なので当たり前?)ため, beginやrbeginを使って最大値, 最小値を$O(\log n)$で参照できます

(x, y)

まずは入力配列の[left, right, height]の要素から[left, -height], [right, height]という要素を作り,これを高さに入れます

つまり, 左端の高さを負, 右端の高さは正とした二次元配列を作ります

この配列をxの大きさに応じてソートします. つまり左の点から見ていくということです

正負で左端か終端か判断

そして, (x, y)の入った配列の要素を見ていきます

  • 負のとき(左端)
    • std::multisetにこの高さを入れます
  • 正のとき(右端)
    • std::multisetに既に高さが入っているので高さを取り出します

ここで忘れてはいけないのは最初に$0$を入れておくことです. 建物がないときの高さは$0$であり必要です

そして, 今までの最小の高さ(高さに負を掛けているので)を現在の最小の高さを比較します. もし異なる時は高さが変化したということなので(x, cur)を答えの配列に格納します

計算量

入力要素の数を$N$とします

  • 空間計算量
    • 配列は入力の倍(負と正に分けるから)の配列が必要になり, std::multisetの分も必要になります
    • $O(N)$
  • 時間計算量
    • 配列の要素に対してそれぞれ$O(\log n)$の操作をするので$O(n \log n)$

C++

class Solution {
public:
  vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<vector<int>> heights;
    for (vector<int> b : buildings) {
      heights.push_back({b[0], -b[2]});
      heights.push_back({b[1], b[2]});
    }
    sort(heights.begin(), heights.end());

    int prev = 0, cur;
    multiset<int> mset {0};
    vector<vector<int>> res;

    for (vector<int> xy : heights) {
      if (xy[1] < 0) mset.insert(-xy[1]);
      else mset.erase(mset.find(xy[1]));

      cur = *mset.rbegin();
      if (prev != cur) {
        res.push_back({xy[0], cur});
        prev = cur;
      }
    }

    return res;
  }
};