题目

在一座城市里，你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。

这座城市对这些新建筑有一些规定：

• 每栋建筑的高度必须是一个非负整数。
• 第一栋建筑的高度 必须 是 0 。
• 任意两栋相邻建筑的高度差 不能超过  1 。

除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 restrictions 的形式给出，其中 restrictions[i] = [idi, maxHeighti] ，表示建筑 idi 的高度 不能超过 maxHeighti 。

题目保证每栋建筑在 restrictions 中 至多出现一次 ，同时建筑 1 不会 出现在 restrictions 中。

请你返回 最高 建筑能达到的 最高高度 。

思路

每一个限制都有可能影响到所有建筑物的最高高度，因此可以这样考虑：

1. 先向右遍历一遍所有的限制，根据左侧一个限制位置的最高高度即可计算出当前限制位置的最高高度。即，如果位置i左侧最近一个限制的位置是j，且已知j的最高高度为h，那么位置i的最高高度就应该是$h+(i-j)$；
2. 再向左遍历一遍所有的限制，按照同样的方法处理一遍所有的限制位置对应的最高高度，即可得到在所有限制下，每个位置可以达到的最高高度。

得到了每个限制位置可以达到的最高高度后，就需要计算答案了，需要注意的是，答案不仅仅是每个限制位置上的最高高度的最大值，而是每一个位置上可能的最高高度的最大值，因此需在两个已知最大高度的相邻限制位置之间求一个可能的最大高度。

如果两个相邻限制位置i和j对应的最大高度分别为$h_i$和$h_j$，那么假设在它中间的位置上有一个最大的高度best，由于题目限制了任意两栋相邻的建筑高度差最大为1，因此best必须满足以下式子：

即可求出best最大为:

之后，对于每两个相邻的限制位置都求一个中间的最高高度best的最大值，即可得到答案。

代码

class Solution:
    def maxBuilding(self, n: int, R: List[List[int]]) -> int:
        R.sort()
        R.insert(0, [1,0]) # 为了求所有的最高高度，需要在左右都加上哨兵
        if R[-1][0] != n:
            R.append([n, n-1])
        
        m = len(R)
        for i in range(1, m):
            R[i][1] = min(R[i][1], R[i-1][1]+(R[i][0]-R[i-1][0]))
        
        for i in range(m-2, 0, -1):
            R[i][1] = min(R[i][1], R[i+1][1]+(R[i+1][0]-R[i][0]))
        
        res = 0
        for i in range(m-1):
            best = (R[i+1][0]-R[i][0]+R[i][1]+R[i+1][1])//2
            res = max(res, best)
        return res