一、题目

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

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

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

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

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

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

示例 1：

输入：n = 5, restrictions = [[2,1],[4,1]]
输出：2
解释：我们可以使建筑高度分别为 [0,1,2,1,2] ，最高建筑的高度为 2 。

示例 2：

输入：n = 6, restrictions = []
输出：5
解释：我们可以使建筑高度分别为 [0,1,2,3,4,5] ，最高建筑的高度为 5 。

示例 3：

输入：n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
输出：5
解释：我们可以使建筑高度分别为 [0,1,2,3,3,4,4,5,4,3] ，最高建筑的高度为 5 。

提示：

• 2 <= n <= 10^9
• 0 <= restrictions.length <= min(n - 1, 10^5)
• 2 <= idi <= n
• idi 是 唯一的 。
• 0 <= maxHeighti <= 10^9

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

二、分析及代码

1. 传递限制

（1）思路

每处高度限制都可能对其左、右所有建筑产生影响，因此可先从左向右、从右向左分别遍历传递建筑的高度限制条件，得到各限制处建筑的最高值，再计算每个区间内建筑的最大高度。

（2）代码

class Solution {
    public int maxBuilding(int n, int[][] restrictions) {
        if (restrictions.length == 0)
            return n - 1;
        Arrays.sort(restrictions, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        int m = restrictions.length;
        int[] h = new int[m + 1];//高度限制处建筑的最大高度
        
        h[0] = 0;//第一栋建筑高度为0
        h[1] = Math.min(restrictions[0][1], restrictions[0][0] - 1);
        for (int i = 1; i < m; i++)//从左向右高度限制
            h[i + 1] = Math.min(restrictions[i][1], h[i] + restrictions[i][0] - restrictions[i - 1][0]);
        for (int i = m - 2; i >= 0; i--)//从右向左高度限制
            h[i + 1] = Math.min(h[i + 1], h[i + 2] + restrictions[i + 1][0] - restrictions[i][0]);

        int ans = h[1] + ((restrictions[0][0] - h[1]) >> 1);
        for (int i = 2; i <= m; i++)//统计各区间最大建筑高度
            ans = Math.max(ans, (restrictions[i - 1][0] - restrictions[i - 2][0] + h[i] + h[i - 1]) >> 1);
        ans = Math.max(ans, h[m] + n - restrictions[m - 1][0]);//最后一栋建筑需单独计算
        return ans;        
    }
}

（3）结果

执行用时 ：61 ms，在所有 Java 提交中击败了 100.00% 的用户；
内存消耗 ：90.7 MB，在所有 Java 提交中击败了 85.44% 的用户。

三、其他

暂无。