LC 1840. 最高建筑高度

https://leetcode-cn.com/problems/maximum-building-height/

其实这题我也不知道怎么搞的，而且我也没有办法证明算法正确。

直觉上就是遍历并且更新每个点上的约束。如果某个点最大高度变化的话，那么可能需要返回去遍历之前点的约束。不过如果这样做的话，那么时间复杂度就会比较高。

换个想法，某个点的最大高度只可能不断减小，随着后面遍历这个上限会不断下降。所以索性我们就不返回约束之前的节点了，而是前序遍历完成之后，再反向遍历去更新约束。

直觉上可以解释为，如果这个约束是单调的话（最大高度只能是递减），那么前后两遍遍历应该是正确的。最后最大高度会处于两个有约束的楼栋之间，这个用个简单公式就可以计算出来。

#!/usr/bin/env python3
# coding:utf-8
# Copyright (C) dirlt

from typing import List
from collections import Counter, defaultdict, deque
from functools import lru_cache
import heapq

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        if not restrictions: return n-1
        restrictions.append((1, 0))
        restrictions.sort(key = lambda x: x[0])


        for i in range(1, len(restrictions)):
            (a, ha) = restrictions[i-1]
            (b, hb) = restrictions[i]
            d = (b - a)
            if hb > (ha + d):
                restrictions[i] = (b, ha + d)

        for i in reversed(range(len(restrictions) - 1)):
            (a, ha) = restrictions[i]
            (b, hb) = restrictions[i+1]
            d = (b - a)
            if ha > (hb + d):
                restrictions[i] = (a, hb + d)

        print(restrictions)

        ans = 0
        for i in range(1, len(restrictions)):
            (a, ha) = restrictions[i-1]
            (b, hb) = restrictions[i]
            d = b - a
            x = (hb - ha + d) // 2
            maxh = ha + x
            # print('({}, {}) & ({}, {}) = {}'.format(a, ha, b, hb, maxh))
            ans = max(ans, maxh)

        ans = max(ans, n - restrictions[-1][0] + restrictions[-1][1])
        return ans