218.天际线问题

[hey-monster]

城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。

天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]

 

示例 1：

输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。
示例 2：

输入：buildings = [[0,2,3],[2,5,3]]
输出：[[0,3],[5,0]]
 

提示：

1 <= buildings.length <= 104
0 <= lefti < righti <= 231 - 1
1 <= heighti <= 231 - 1
buildings 按 lefti 非递减排序

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/the-skyline-problem
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：堆（优先队列） + 扫描线
用扫描线从左往右扫描，遇到左上角时，将其与对应的高度放入堆中；继续扫描，当高度发生变化时，说明找到了一段结果，输出；
继续扫描，遇到右上角时，说明这个矩形已经扫过了，需将这个高度从堆中删除；

需要的数据结构
1、一个数组保存：
每个矩形的左上角x坐标、高度，右上角坐标、高度；
对齐左上角的高度取负值，用于区分左右上角
2、一个优先队列：
用于保存高度值（支持插入、删除任意值、获得最大值）
3、前最大值：
用于记录前一段的楼高度，当其改变时，说明前一段已经结束。

注意：
1、数组中进行排队时，除了按照x坐标从小到大依次存放外，当为左上角且x相同时，需按照高度值从大到小存放（因为如果小的在前面，则放入堆中时，可能改变堆的最大值，而这个值本该是隐藏其他矩形后面，造成结果错误）
2、比较函数根据传参不同，里面的写法也不同，要区分是数组还是指针

int arrayCmp(const void* a, const void* b){
    int ret;
    int *tmp1 = (int*)a;
    int *tmp2 = (int*)b;
    ret = tmp1[0] - tmp2[0];  /* x坐标小的放前面 */
    if(ret == 0){
        ret = -tmp2[1] + tmp1[1];   /* x坐标相同的，高度大的放前面 */
    }
    return ret;
}
/* 大根堆操作 */
struct MaxHeap {
    int* ArrayPtr;
    int Size;
    int Capacity;
};
struct MaxHeap* HeapInit(int MaxSize){
    struct MaxHeap* H = malloc(sizeof(struct MaxHeap));
    H->Capacity = MaxSize;
    H->Size = 0;
    H->ArrayPtr = malloc(sizeof(int) * (MaxSize + 1));
    H->ArrayPtr[0] = INT_MAX;   /* 哨兵 */
    return H;
}
bool IsHeapFull(struct MaxHeap* H){
    if(H->Size >= H->Capacity){
        return true;
    }
    return false;
}
bool IsHeapEmpty(struct MaxHeap* H){
    if(H->Size == 0){
        return true;
    }
    return false;
}
void HeapInsert(struct MaxHeap* H, int value){
    if(IsHeapFull(H))   return;
    int i = ++H->Size;
    for( ; H->ArrayPtr[i / 2] < value; i /= 2){
        H->ArrayPtr[i] = H->ArrayPtr[i / 2];
    }
    H->ArrayPtr[i] = value;
}
int HeapDeleteMax(struct MaxHeap* H){
    int Parent, Child;
    int MaxNum, temp;
    temp = H->ArrayPtr[H->Size--];
    MaxNum = H->ArrayPtr[1];
    for(Parent = 1; Parent * 2 <= H->Size; Parent = Child){
        Child = Parent * 2;
        if(Child != H->Size && H->ArrayPtr[Child] < H->ArrayPtr[Child + 1]){
            Child++;
        }
        if(temp >= H->ArrayPtr[Child]){
            break;
        }else{
            H->ArrayPtr[Parent] = H->ArrayPtr[Child];
        }
    }
    H->ArrayPtr[Parent] = temp;
    return MaxNum;
}
void HeapDeleteX(struct MaxHeap* H, int x){
    int i;
    for( i = 1; i <= H->Size; ++i){
        if(H->ArrayPtr[i] == x){
            break;
        }
    }
    if(i > H->Size){
        return;
    }
    for(; i != 1; i /= 2){
        H->ArrayPtr[i] = H->ArrayPtr[i / 2];
    }
    H->ArrayPtr[i] = INT_MAX;
    HeapDeleteMax(H);
}
int HeapGetMax(struct MaxHeap* H){
    if(H->Size > 0){
        return H->ArrayPtr[1];
    }
    return 0;
}
void HeapPrint(struct MaxHeap* H){
    for(int i = 1; i <= H->Size; ++i){
        printf(" %d \n", H->ArrayPtr[i]);
    }
}
int** getSkyline(int** buildings, int buildingsSize, int* buildingsColSize, int* returnSize, int** returnColumnSizes){
    int vetex[buildingsSize * 2][2];            /* 从小到大排序处理后的数组 */
    int vetexSize = buildingsSize * 2;
    for(int i = 0; i < buildingsSize; ++i){
        vetex[i*2][0] = buildings[i][0];        /* 左上点，保存高度为负值 */
        vetex[i*2][1] = -buildings[i][2];
        vetex[i*2 + 1][0] = buildings[i][1];    /* 右上点，保存高度为正值 */
        vetex[i*2 + 1][1] = buildings[i][2];
    }
    qsort(vetex, vetexSize, sizeof(vetex[0]), arrayCmp);
    /*for(int i = 0; i < vetexSize; ++i){
        printf(" %d, %d \n", vetex[i][0], vetex[i][1]);
    }*/

    struct MaxHeap* H = HeapInit(vetexSize);
    int** ret = (int**)malloc(sizeof(int*) * vetexSize);
    int retSize = 0;
    int lastHeight = 0;
    for(int i = 0; i < vetexSize; ++i){
        if(vetex[i][1] < 0){            /* 左边界,入堆 */
            HeapInsert(H, -vetex[i][1]);
        }else{                          /* 右边界,删除 */
            HeapDeleteX(H, vetex[i][1]);
        }
        //HeapPrint(H);
        if(lastHeight != HeapGetMax(H)){   /* 当前最高发生了变化 */
            lastHeight = HeapGetMax(H);
            ret[retSize] = (int*)malloc(sizeof(int) * 2);
            ret[retSize][0] = vetex[i][0];
            ret[retSize][1] = HeapGetMax(H);
            retSize++;
        }
    }
    *returnColumnSizes = (int*)malloc(sizeof(int) * retSize);
    for(int i = 0; i < retSize; ++i){
        (*returnColumnSizes)[i] = 2;
    }
    *returnSize = retSize;
    return ret;
}