131. The Skyline Problem

https://leetcode.com/problems/the-skyline-problem/

<code>
from heapq import heappush, heappop
import collections
class Solution:
    def buildingOutline(self, buildings):
        # init
        pre_h = 0
        xs = []
        for x1, x2, y in buildings:
            xs.append((x1, 1, y))
            xs.append((x2, -1, y))
        xs.sort()
        h, sky = [], []
        del_log = collections.defaultdict(int)
        n = len(xs)
        for i, (x, flag, y) in enumerate(xs):
            if flag == 1:
                heappush(h, -y)
            elif flag == -1:
                self.del_y(-y, h, del_log)
            curt_h = -h[0] if h else 0
            if i == n - 1 or x != xs[i + 1][0]:
                if curt_h != pre_h:
                    sky.append((x, curt_h))
                    pre_h = curt_h
        res = []
        for i in range(len(sky) - 1):
            x, y = sky[i]
            if y == 0:
                continue
            x2 = sky[i + 1][0]
            res.append((x, x2, y))
        return res

    def del_y(self, y, h, del_log):
        if y != h[0]:
            del_log[y] += 1
            return

        heappop(h)

        while h and h[0] in del_log:
            v = heappop(h)
            del_log[v] -= 1
            if del_log[v] == 0:
                del del_log[v

way 1: sweep_line + heap + delete log (逻辑删除),
封装: del_height(height, h, del_log) 帮助实现 log n 删除任一元素.

先用扫描线排序, 每个建筑(起止点)顺序进出 heap 堆,
相同的 x 走完, 判断 max_y, 如果跟之前的 pre_y 有变化, 记录 (x, max_y) 为一个新拐点.
- 用 heap 返回最高点 max_y,
- if i == n - 1 or x != next_x; next_x = xs[i + 1][0] # 检查相同的 x 是否走完,

way 2: sweep_line + tree map, counter[h] = k,
用平衡二叉树返回最大值 max_y, 和查找更改一个值的个数(逻辑删除).