最高建筑高度

标签: 数组 数学

难度: Hard

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

Submission

运行时间: 206 ms

内存: 43.3 MB

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        restrictions.sort(key=lambda x: x[0])
        for ri in range(len(restrictions) - 2, -1, -1):
            j = restrictions[ri+1][0]
            i = restrictions[ri][0]
            restrictions[ri][1] = min(restrictions[ri][1], restrictions[ri+1][1] + j - i)
        res = 0
        i = 1
        h = 0
        for ri in range(len(restrictions)):
            j = restrictions[ri][0]
            hh = restrictions[ri][1]
            if hh - h >= j - i:
                hh = h + j - i
                res = max(res, hh)
            else:
                y = hh + j - i - h
                x = y // 2
                res = max(res, h + x)
            i = j
            h = hh
        res = max(res, h + n - i)
        return res

Explain

此题解采用了从左至右和从右至左两次扫描的方法来处理建筑的高度限制。首先，按照建筑编号对限制进行排序。然后，从右向左对限制进行一次扫描，以确保每个建筑的高度限制不会因为右侧建筑的高度限制而变得不可能。在这个过程中，每个建筑的最大高度会根据其右侧建筑的最大高度和两建筑间的距离进行调整。接着，从左至右遍历所有建筑，利用当前建筑的高度和下一个受限制建筑的高度以及两者之间的距离来逐步确定每个建筑的实际高度，并计算可能的最大高度。最终，包括最后一个建筑到第n个建筑的高度差也被考虑在内。

时间复杂度: O(r log r)

空间复杂度: O(r)

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        restrictions.sort(key=lambda x: x[0]) # 按建筑编号排序
        # 从右向左更新高度限制以适应右侧建筑的限制
        for ri in range(len(restrictions) - 2, -1, -1):
            j = restrictions[ri+1][0]
            i = restrictions[ri][0]
            restrictions[ri][1] = min(restrictions[ri][1], restrictions[ri+1][1] + j - i)
        res = 0
        i = 1
        h = 0
        # 从左向右计算每个建筑的高度，并更新最大可能高度
        for ri in range(len(restrictions)):
            j = restrictions[ri][0]
            hh = restrictions[ri][1]
            if hh - h >= j - i: # 如果高度差允许
                hh = h + j - i
                res = max(res, hh)
            else: # 如果高度差不允许，使用中点高度
                y = hh + j - i - h
                x = y // 2
                res = max(res, h + x)
            i = j
            h = hh
        res = max(res, h + n - i) # 包括最后一个建筑到第n个建筑的高度差
        return res

Explore

排序是必要的，因为题目要求在进行高度计算时，需要确保从一个建筑到下一个建筑的高度增加或减少不超过1。如果限制没有按照建筑编号顺序排列，那么在从左到右或从右到左计算建筑高度时，可能会错过重要的高度限制信息，导致计算错误。通过排序，我们可以按顺序处理每栋建筑的高度限制，确保每步计算都考虑到了正确的限制条件。

这个公式的目的是确保高度限制的可行性，防止因右侧建筑的高度限制导致当前建筑的限制不可能达到。这里，`restrictions[ri][1]`是当前建筑的最高高度限制，`restrictions[ri+1][1]`是右侧建筑的最高高度限制，`j - i`是两栋建筑间的编号差。由于相邻建筑的高度差不能超过1，所以从右侧建筑到当前建筑的最大可能高度是`restrictions[ri+1][1] + j - i`。因此，要确保当前建筑的限制是合理的，我们取`restrictions[ri][1]`和`restrictions[ri+1][1] + j - i`的最小值作为新的高度限制。

这个条件用于检查在不违反高度差规则的情况下，是否能直接从当前建筑增加到下一个受限建筑的最大高度。这里，`hh`是下一个受限建筑的最高高度限制，`h`是当前建筑的高度，`j - i`是两栋建筑间的编号差。如果`hh - h >= j - i`成立，意味着从当前建筑到下一个建筑的高度可以线性增加而不超过`hh`。如果条件不满足，即`hh - h < j - i`，则说明直接增加到`hh`会导致某些步骤中高度差超过1，此时需要使用中点高度，即在允许的高度差范围内尽可能增加高度，然后计算这种情况下的最大可能高度。