在 Python 中查找最大建筑高度的程序

假设我们有一个值 n 和另一个称为限制的对列表。我们想在一个城市建造 n 座新建筑。但是限制很少。我们可以建在一条线上，建筑物的标签从 1 到 n。限制有两个参数，因此限制[i] = (id_i, max_height_i) 表示 id_i 的高度必须小于或等于 max_height_i。城市对新建筑高度的限制如下 -

• 每个建筑物的高度必须为 0 或正值。

• 第一个建筑物高度必须为 0。

• 任意两座相邻建筑物高度之差不能超过1。

我们必须找到最高建筑物的最大可能高度。

所以，如果输入像 n = 5，restrictions = [[2,1],[4,3]]，那么输出将是 4，因为我们必须找到最大可能的高度，所以它可以是 4，如图所示图。

示例

让我们看看以下实现以更好地理解

def solve(n, restrictions):
   if not restrictions:
      return n-1
   resi = sorted(restrictions, key = lambda x:x[0])

   k = 0
   idx = 1
   for re in resi:
      re[1] = min(re[1], k+re[0]-idx)
      k = re[1]
      idx = re[0]
   k = resi[-1][1]
   idx = resi[-1][0]
   resi.reverse()
   for re in resi[1:]:
      re[1] = min(re[1], k-re[0]+idx)
      k = re[1]
      idx = re[0]
   resi.reverse()

   f = 0
   idx = 1
   res = 0
   for re in resi:
      ff = min(f+re[0]-idx, re[1])
      res = max(res, (re[0] - idx + f + ff) //2)
      idx = re[0]
      f = ff
   return max(f+n-idx,res)

n = 5
restrictions = [[2,1],[4,3]]
print(solve(n, restrictions))

输入

5, [[2,1],[4,3]]

4