[Java] UVa 105 The Skyline Problem

題目連結

題意:
有好幾棟高度不一的大樓，我們看過去是個 x軸從左到右，y軸大樓樓高的平面，大樓有遠近差別，x座標可能會重疊。假設有條Skyline，我是想像有一條超大的布，要把所有大樓蓋起來，要問布會蓋到那些位置(求布蓋到大樓形成直角的地方，也就是高度有落差的點座標)

輸入測資有好幾行(1 ~ 5000)，每一行(L, H, R)分別是一棟大樓的位置左、高度與右，輸出是所有Skyline(x, y)座標。(可以參考題目範例的右圖，取每個直線的後者座標)

我的解法:
我用一個陣列去紀錄每個點的最高位置(因應建築物重疊只會取最高點)，index就是x座標。另外用max，min紀錄出現最左、最右的x位置，做輸出的臨界值依據。輸出時，從min開始，宣告一個變數紀錄現在的高度，只要有變化(當前不等於上一個)就是有高度落差，就輸出。

要注意圖上出現直線的地方都是取後者的點，所以在紀錄時同一個高度我只記錄到建築物最右的前一個位置，連貫的地方才不會出錯(舉例:一個大樓右側高20，在24位置，另一個相鄰的大樓左側高10，也是24，此時應該輸出24 10)

import java.util.Scanner;

public class Main {
 public static void main(String[] args) {
  try{
            int L, H, R;
            int min = 10000, max = 0;
            
            int tall[] = new int[10001];
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
            
             L = in.nextInt();
             H = in.nextInt();
             R = in.nextInt();
             
             for(int i = L; i < R; i++) {
              if(H > tall[i])
               tall[i] = H;
             }
             if(R > max)
              max = R;
             if(L < min)
              min = L;
             
            }
            
            int now = tall[min];
            System.out.print(min + " " + now);
            
            for(int j = min; j <= max; j++){
             if(tall[j] != now) {
              now = tall[j];
              System.out.print(" " + j + " " + now);
             }
            }
            System.out.println();
            
        }catch(Exception e){
            System.out.println("Input error!");
        }
    }
}