How do I handle the maximum building height when no restrictions are provided?

Without restrictions, the maximum height for each building increases sequentially. You simply assign heights based on the building index.

What pattern should I use to approach the Maximum Building Height problem?

This problem follows the 'Array plus Math' pattern, combining sorting with mathematical reasoning to distribute building heights.

How do I calculate the tallest building in the city given restrictions?

By calculating the maximum height that can be assigned to each building while respecting the restrictions and height differences, you can determine the tallest building.

What is the time complexity of the Maximum Building Height solution?

The time complexity is O(m log m), where m is the number of restrictions. Sorting the restrictions dominates the complexity.

How do I handle edge cases in this problem?

Edge cases include scenarios with no restrictions, restrictions on buildings at the ends, or multiple restrictions on the same building. These need special handling during the calculation of the maximum building heights.

#1840

Hard

auto_awesome数组·数学

LeetCode 题解工作台

最高建筑高度

在一座城市里，你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。这座城市对这些新建筑有一些规定：每栋建筑的高度必须是一个非负整数。第一栋建筑的高度必须是 0 。任意两栋相邻建筑的高度差不能超过 1 。除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数…

数组数学排序

题目描述

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

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

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

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

题目保证每栋建筑在 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 <= id_i <= n
id_i 是 唯一的 。
0 <= maxHeight_i <= 10⁹

lightbulb

解题思路

方法一：排序 + 数学

首先，我们将所有的限制条件按照建筑物的编号从小到大排序。

然后我们从左到右遍历所有的限制条件，对于每个限制条件，我们可以得到一个最高高度的上界，即 $r_i[1] = \min(r_i[1], r_{i-1}[1] + r_i[0] - r_{i-1}[0])$ ，其中 $r_i$ 表示第 $i$ 个限制条件，而 $r_i[0]$ 和 $r_i[1]$ 分别表示建筑物的编号以及建筑物的最高高度的上界。

然后我们从右到左遍历所有的限制条件，对于每个限制条件，我们可以得到一个最高高度的上界，即 $r_i[1] = \min(r_i[1], r_{i+1}[1] + r_{i+1}[0] - r_i[0])$ 。

这样，我们就得到了每个限制建筑物的最高高度的上界。

题目求的是最高建筑物的高度，我们可以枚举相邻两个限制条件之间的建筑物 $i$ 和 $i+1$ ，要使得高度最大，那么高度应该是先增大后减小，假设最大高度为 $t$ ，那么 $t - r_i[1] + t - r_{i+1}[1] \leq r_{i+1}[0] - r_i[0]$ ，即 $t \leq \frac{r_i[1] + r_{i+1}[1] + r_{i+1}[0] - r_{i}[0]}{2}$ ，我们取所有的 $t$ 中的最大值即可。

时间复杂度 $O(m \times \log m)$ ，空间复杂度 $O(m)$ 。其中 $m$ 为限制条件的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        r = restrictions
        r.append([1, 0])
        r.sort()
        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])
        ans = 0
        for i in range(m - 1):
            t = (r[i][1] + r[i + 1][1] + r[i + 1][0] - r[i][0]) // 2
            ans = max(ans, t)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate can efficiently use sorting to handle restrictions.
question_mark
Candidate shows understanding of how to calculate height differences between buildings.
question_mark
Candidate demonstrates problem-solving ability by iterating through the buildings correctly.

warning

常见陷阱

外企场景

error
Failing to handle cases where there are no restrictions.
error
Incorrectly calculating the height difference between adjacent buildings.
error
Overlooking edge cases where restrictions are placed on buildings at the ends of the sequence.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider larger values for n and test performance optimizations.
arrow_right_alt
Vary the number of restrictions and test edge cases like no restrictions or all buildings restricted.
arrow_right_alt
Modify the problem by allowing multiple restrictions per building and determining how that affects the maximum height calculation.

help

常见问题

外企场景

继续练习

#1878 矩阵中最大的三个菱形和 #1686 石子游戏 VI #1998 数组的最大公因数排序