任意一栋楼的最大高度受限于从左开始受限制的楼的高度以及从右开始受限制的楼的高度，因此预处理出来：

$f[i]$：从左开始到第$i$条直线的截距最小值
$g[i]$：从右开始到第$i$条直线的截距最小值

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& h) {
        typedef long long LL;
        h.push_back({1 , 0});//第1栋楼的高度是0
        sort(h.begin() , h.end());
        if(h.back()[0] != n) h.push_back({n , n - 1});//显然最后一栋楼的不超过n-1，如果不存在第n栋楼的限制则加入。
        int m = h.size();
        vector<LL> f(m + 1 , INT_MAX) , g(m + 1 , INT_MAX);
        f[0] = -1;//第1栋楼的高度是0，因此第1条直线的截距是-1
        for(int i = 1 ; i < m ; i++)
        {
            LL x = h[i][0] , y = h[i][1];
            LL b = y - x;
            f[i] = min(f[i - 1] , b);
        }

        for(int i = m - 1 ; i >= 0 ; i--)
        {
            LL x = h[i][0] , y = h[i][1];
            LL b = x + y;
            g[i] = min(g[i + 1] , b);
        }

        LL res = 0;
        for(int i = 0 ; i < m ; i++)
        {
            LL x = h[i][0];
            res = max(res , min(x + f[i] , -x + g[i]));//到第i个有要求的建筑物时，所能取到的最高高度是min(x + f[i] , -x + g[i]);
            //与此同时，为与第i-1栋和第i栋有要求的建筑物之间的最大高度取决于正负两条对角线的交点
            if(i)
            {
                //求得交点(X,Y)
                LL Y = (f[i - 1] + g[i]) / 2;
                LL X = Y - f[i - 1];
                if(X >= h[i - 1][0] && X <= h[i][0])
                    res = max(res , Y);
            }
        }
        return res;
    }
};