输入#

整数 n，二维整数数组 restrictions

输出#

最高建筑能达到的最大高度

约束条件#

1. 2 <= n <= 10^9
2. 0 <= restrictions.length <= min(n - 1, 10^5)
3. 2 <= idi <= n，idi 互不相同
4. 0 <= maxHeighti <= 10^9

示例1#

1
input: n = 5, restrictions = [[2,1],[4,1]]
2
output: 2

解释：可使建筑高度为 [0,1,2,1,2]，最高建筑高度为 2。

示例2#

1
input: n = 6, restrictions = []
2
output: 5

解释：无额外限制时，高度可依次为 [0,1,2,3,4,5]，最高为 5。

示例3#

1
input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
2
output: 5

解释：可使建筑高度为 [0,1,2,3,3,4,4,5,4,3]，最高为 5。

从直观做法出发#

最容易想到的是：对每一栋建筑 i，从左侧（建筑 1 高度 0）和右侧（建筑 n 无上限）分别推算它能达到的最大高度，再取两者较小值。但关键建筑有 10^5 个、总栋数有 10^9 个，逐栋计算显然不可行。

观察示例可以发现：高度上限只出现在 restrictions 给出的位置，其余建筑的高度由相邻关系和这些「卡点」共同决定。因此真正需要关心的，只有有限个关键位置——起点、终点，以及所有受限建筑。

关键观察：峰值只出现在相邻关键位置之间#

任意合法高度序列中，全局最高点要么落在某个关键位置上，要么落在两个关键位置之间的某栋建筑上。

考虑相邻关键位置 $x_i$ 与 $x_{i+1}$，其间距离为 $d = x_{i+1} - x_i$。若位置 $x_i$ 处高度上界为 $h_i$，$x_{i+1}$ 处为 $h_{i+1}$，则这段区间内能抬起的最高「山峰」高度为：

直觉上：从左侧以不超过 $h_i$ 的高度出发，以每步最多 $+1$ 的斜率向中间爬升，同时从右侧以不超过 $h_{i+1}$ 的高度以每步最多 $+1$ 向中间爬升，两坡在中点相遇时即得峰值。最终答案就是所有区间 peak 的最大值。

因此问题归结为两步：

1. 求出每个关键位置在全局约束下的高度上界 $h[i]$；
2. 枚举相邻关键位置对，用上式取最大值。

预处理：补全边界并排序#

restrictions 中不含建筑 1 和建筑 n，但它们是天然的关键点。补入边界后统一排序：

• [1, 0]：建筑 1 高度固定为 0；
• [n, inf]：建筑 n 无高度上限（用 inf 表示）。

1
restrictions += [[1, 0], [n, inf]]
2
restrictions.sort()

以示例 1（n = 5, restrictions = [[2,1],[4,1]]）为例，排序后得到：

正向扫描：来自左侧的上界#

从左向右，假设在位置 $x_{i-1}$ 处高度最多为 $h[i-1]$，则走到 $x_i$（距离 $x_i - x_{i-1}$）时，理论上限为 $h[i-1] + (x_i - x_{i-1})$，再与该位置的显式限制取小：

示例 1 正向扫描：

此时 h[3]=2 只考虑了从左而来的约束，尚未被右侧限制收紧。

反向扫描：来自右侧的上界#

再从右向左，用对称逻辑收紧上界。在位置 $x_{i+1}$ 处高度最多为 $h[i+1]$，则位置 $x_i$ 处来自右侧的上界为 $h[i+1] + (x_{i+1} - x_i)$，与当前值取小：

示例 1 反向扫描：

两轮扫描后，$h[i]$ 即为位置 $x_i$ 在全部约束下的高度上界。

段内取峰值#

最后枚举每对相邻关键位置，套用峰值公式：

1
max((x[i+1] - x[i] + h[i] + h[i+1]) // 2 for i in range(m - 1))

示例 1 各段：

最大值为 2，与示例输出一致。

复杂度#

• 时间复杂度：$O(m \log m)$，$m$ 为关键位置数（restrictions.length + 2），排序 dominates
• 空间复杂度：$O(m)$，存储高度上界数组

代码#

1
from math import inf
2

3
class Solution:
4
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
5
        restrictions += [[1, 0], [n, inf]]
6
        restrictions.sort()
7

8
        m = len(restrictions)
9
        h = [0] * m
10

11
        for i in range(1, m):
12
            h[i] = min(h[i - 1] + restrictions[i][0] - restrictions[i - 1][0], restrictions[i][1])
13
        for i in range(m - 2, -1, -1):
14
            h[i] = min(h[i], h[i + 1] + restrictions[i + 1][0] - restrictions[i][0])
15

16
        return max(restrictions[i + 1][0] - restrictions[i][0] + h[i] + h[i + 1] for i in range(m - 1)) // 2

合并位置 n 的重复条目#

若 restrictions 中已包含 [n, maxHeight]，补入 [n, inf] 后排序会出现两个位置为 n 的条目。正确性不受影响（第二趟正向扫描距离为 0，h 不变），但可以在排序后合并：同一位置取 limit 的较小值。

1
restrictions += [[1, 0], [n, inf]]
2
restrictions.sort()
3
merged = [restrictions[0]]
4
for x, lim in restrictions[1:]:
5
    if merged[-1][0] == x:
6
        merged[-1][1] = min(merged[-1][1], lim)
7
    else:
8
        merged.append([x, lim])
9
restrictions = merged

拆出位置与限制，减少二维下标#

将 restrictions 拆为 xs 与 limits 两个数组，循环体更紧凑，也避免反复写 restrictions[i][0]：

1
from math import inf
2

3
class Solution:
4
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
5
        restrictions += [[1, 0], [n, inf]]
6
        restrictions.sort()
7
        xs = [x for x, _ in restrictions]
8
        limits = [lim for _, lim in restrictions]
9
        m = len(xs)
10
        h = [0] * m
11

12
        for i in range(1, m):
13
            h[i] = min(h[i - 1] + xs[i] - xs[i - 1], limits[i])
14
        for i in range(m - 2, -1, -1):
15
            h[i] = min(h[i], h[i + 1] + xs[i + 1] - xs[i])
16

17
        return max(xs[i + 1] - xs[i] + h[i] + h[i + 1] for i in range(m - 1)) // 2

语义与原写法完全一致，仅将「关键位置」与「高度上限」解耦，便于阅读与调试。