【LeetCode 218】The Skyline Problem / 题解

Origin

Statement

你要设计一个程序去帮助一个建筑师绘制在城市里特定区域建筑的轮廓线。为了使问题易于处理，所有的建筑的外形都是矩形的，且它们共享同一个地面（这个城市建设在同一个非常平坦的地面上）。这城市看上去是两维的。每幢建筑有一个三元组（Li,Hi,Ri）其中Li和Ri分别是建筑的左坐标和右坐标，Hi就是建筑的高度。在下方所示的图表中左边用建筑物的三元组(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)表示，右边用轮廓线的顺序（1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0）表示：

Idea

首先有一段吐槽：

OIer 和 ACMer 的思维果然有很大的区别。。。

我看到这道题的第一想法就是线段树维护区间最大值，就是提高-的水平，然而。。。

这道题在 LeetCode 上评级为 Hard ，而 LintCode 上评级甚至达到了 Super。。。
工业级别的代码也非常可怕：

public class Solution {
    public List getSkyline(int[][] buildings) {
        List results = new ArrayList<>();
        PriorityQueue rightHeap = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return Integer.compare(buildings[i1][1], buildings[i2][1]);
            }
        });
        PriorityQueue heightHeap = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return Integer.compare(buildings[i2][2], buildings[i1][2]);
            }
        });
        int prev = 0;
        for(int i = 0; i < buildings.length; i++) {
            while (!rightHeap.isEmpty() && buildings[rightHeap.peek()][1] < buildings[i][0]) {
                int b = rightHeap.poll();
                heightHeap.remove(b);
                while (!rightHeap.isEmpty() && buildings[rightHeap.peek()][1] == buildings[b][1]) {
                    b = rightHeap.poll();
                    heightHeap.remove(b);
                }
                int height = heightHeap.isEmpty() ? 0 : buildings[heightHeap.peek()][2];
                if (height != prev) {
                    int[] result = new int[2];
                    result[0] = buildings[b][1];
                    result[1] = height;
                    results.add(result);
                    prev = height;
                }
            }
            while (!rightHeap.isEmpty() && buildings[rightHeap.peek()][1] == buildings[i][0]) {
                int b = rightHeap.poll();
                heightHeap.remove(b);
            }
            rightHeap.offer(i);
            heightHeap.offer(i);
            while (i < buildings.length - 1 && buildings[i][0] == buildings[i + 1][0]) {
                i++;
                rightHeap.offer(i);
                heightHeap.offer(i);
            }
            int height = buildings[heightHeap.peek()][2];
            if (height != prev) {
                int[] result = new int[2];
                result[0] = buildings[i][0];
                result[1] = height;
                results.add(result);
                prev = height;
            }
        }

        while (!rightHeap.isEmpty()) {
            int b = rightHeap.poll();
            heightHeap.remove(b);
            while (!rightHeap.isEmpty() && buildings[rightHeap.peek()][1] == buildings[b][1]) {
                b = rightHeap.poll();
                heightHeap.remove(b);
            }
            int height = heightHeap.isEmpty() ? 0 : buildings[heightHeap.peek()][2];
            if (height != prev) {
                int[] result = new int[2];
                result[0] = buildings[b][1];
                result[1] = height;
                results.add(result);
                prev = height;
            }
        }
        return results;
    }

以下是我写的线段树：

Code

#include 
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define maxn 10010
using namespace std;
int tree[maxn*4],lazy[maxn*4],wide,tem,ans[maxn];
void chma(int &x,int y){x=max(x,y);}
void pushdown(int p){
    int t=lazy[p];lazy[p]=0;
    chma(tree[ls],t),chma(tree[rs],t);
    chma(lazy[ls],t),chma(lazy[rs],t);
}
void insert(int l,int r,int L,int R,int k,int p){
    if (l>R||r=L&&r<=R){
        chma(lazy[p],k),chma(tree[p],k);
        return;
    }
    if (lazy[p]) pushdown(p);
    insert(l,mid,L,R,k,ls),insert(mid+1,r,L,R,k,rs);
}
void query(int l,int r,int p){
    if (l==r){
        ans[l]=tree[p];
        return;
    }
    if (lazy[p]) pushdown(p);
    query(l,mid,ls),query(mid+1,r,rs);
}
int main(){
    ios::sync_with_stdio(false);
    int x,y,z;
    while(cin>>x>>z>>y){
        wide=max(wide,y);
        insert(1,10000,x,y-1,z,1);
    }
    query(1,10000,1);
    for (int i=1;i<=wide;i++){
        if (ans[i]==tem) continue;
        cout<