1840. 最高建筑高度Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

在一座城市里，你需要建 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⁹
0 <= restrictions.length <= min(n - 1, 10⁵)
2 <= idi <= n
idi 是唯一的。
0 <= maxHeighti <= 10⁹

# 思路

Arrays.sort

# 解法

class Solution {
    public static int maxBuilding(int n, int[][] restrictions) {
        Arrays.sort(restrictions, (o1, o2) -> o1[0] + o1[1] - o2[0] - o2[1]);
        int result = 0, b = -1;
        for (int[] restriction : restrictions) {
            if (restriction[1] - restriction[0] < b) {
                result = Math.max(result, (restriction[0] + restriction[1] + b) >>> 1);
                b = restriction[1] - restriction[0];
            }
        }
        return Math.max(result, n + b);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 总结

分析出几种情况，然后分别对各个情况实现

#Java