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 <= 10^9
  • 0 <= restrictions.length <= min(n - 1, 10^5)
  • 2 <= idi <= n
  • idi 是唯一的
  • 0 <= maxHeighti <= 10^9

解题思路

这道题的核心思路是利用双向约束传播来求解最优高度。由于相邻建筑高度差不能超过1，我们需要考虑限制条件对其他位置的影响。

解题思路：

  1. 预处理限制条件：将所有限制条件按位置排序，并在开头和结尾添加虚拟限制点(1,0)和(n,n-1)，方便处理边界情况。

  2. 左到右传播：从左向右遍历限制点，确保每个限制点的高度不会因为左边的限制而变得不可达。如果当前限制点的高度小于从左边传播过来的最小高度，则更新当前限制的高度。

  3. 右到左传播：从右向左遍历限制点，同样确保每个限制点的高度不会因为右边的限制而变得不可达。

  4. 计算最大高度：在相邻两个限制点之间，建筑可以达到的最大高度是两端限制高度和距离约束共同决定的。对于位置i和j之间的任意位置k，其最大高度为两端高度加上到达该位置的最大步数。

  5. 优化计算：相邻两个限制点之间的最大高度可以通过公式计算：max(leftHeight + distance, rightHeight + distance) / 2，但需要考虑实际的约束条件。

这种方法的时间复杂度主要取决于限制点的数量，而不是建筑总数n，因此即使n很大也能高效求解。

代码实现

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        vector<pair<int, int>> limits;
        limits.push_back({1, 0});
        for (auto& r : restrictions) {
            limits.push_back({r[0], r[1]});
        }
        limits.push_back({n, n - 1});
        
        sort(limits.begin(), limits.end());
        
        // Left to right pass
        for (int i = 1; i < limits.size(); i++) {
            int dist = limits[i].first - limits[i-1].first;
            limits[i].second = min(limits[i].second, limits[i-1].second + dist);
        }
        
        // Right to left pass
        for (int i = limits.size() - 2; i >= 0; i--) {
            int dist = limits[i+1].first - limits[i].first;
            limits[i].second = min(limits[i].second, limits[i+1].second + dist);
        }
        
        int maxHeight = 0;
        for (int i = 0; i < limits.size() - 1; i++) {
            int pos1 = limits[i].first, h1 = limits[i].second;
            int pos2 = limits[i+1].first, h2 = limits[i+1].second;
            int dist = pos2 - pos1;
            
            maxHeight = max(maxHeight, max(h1, h2));
            maxHeight = max(maxHeight, (h1 + h2 + dist) / 2);
        }
        
        return maxHeight;
    }
};

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        limits = [[1, 0]]
        for r in restrictions:
            limits.append(r)
        limits.append([n, n - 1])
        
        limits.sort()
        
        # Left to right pass
        for i in range(1, len(limits)):
            dist = limits[i][0] - limits[i-1][0]
            limits[i][1] = min(limits[i][1], limits[i-1][1] + dist)
        
        # Right to left pass
        for i in range(len(limits) - 2, -1, -1):
            dist = limits[i+1][0] - limits[i][0]
            limits[i][1] = min(limits[i][1], limits[i+1][1] + dist)
        
        max_height = 0
        for i in range(len(limits) - 1):
            pos1, h1 = limits[i]
            pos2, h2 = limits[i+1]
            dist = pos2 - pos1
            
            max_height = max(max_height, h1, h2)
            max_height = max(max_height, (h1 + h2 + dist) // 2)
        
        return max_height

public class Solution {
    public int MaxBuilding(int n, int[][] restrictions) {
        var limits = new List<int[]>();
        limits.Add(new int[]{1, 0});
        foreach (var r in restrictions) {
            limits.Add(r);
        }
        limits.Add(new int[]{n, n - 1});
        
        limits.Sort((a, b) => a[0].CompareTo(b[0]));
        
        // Left to right pass
        for (int i = 1; i < limits.Count; i++) {
            int dist = limits[i][0] - limits[i-1][0];
            limits[i][1] = Math.Min(limits[i][1], limits[i-1][1] + dist);
        }
        
        // Right to left pass
        for (int i = limits.Count - 2; i >= 0; i--) {
            int dist = limits[i+1][0] - limits[i][0];
            limits[i][1] = Math.Min(limits[i][1], limits[i+1][1] + dist);
        }
        
        int maxHeight = 0;
        for (int i = 0; i < limits.Count - 1; i++) {
            int pos1 = limits[i][0], h1 = limits[i][1];
            int pos2 = limits[i+1][0], h2 = limits[i+1][1];
            int dist = pos2 - pos1;
            
            maxHeight = Math.Max(maxHeight, Math.Max(h1, h2));
            maxHeight = Math.Max(maxHeight, (h1 + h2 + dist) / 2);
        }
        
        return maxHeight;
    }
}

var maxBuilding = function(n, restrictions) {
    const limits = [[1, 0]];
    for (const r of restrictions) {
        limits.push(r);
    }
    limits.push([n, n - 1]);
    
    limits.sort((a, b) => a[0] - b[0]);
    
    // Left to right pass
    for (let i = 1; i < limits.length; i++) {
        const dist = limits[i][0] - limits[i-1][0];
        limits[i][1] = Math.min(limits[i][1], limits[i-1][1] + dist);
    }
    
    // Right to left pass
    for (let i = limits.length - 2; i >= 0; i--) {
        const dist = limits[i+1][0] - limits[i][0];
        limits[i][1] = Math.min(limits[i][1], limits[i+1][1] + dist);
    }
    
    let maxHeight = 0;
    for (let i = 0; i < limits.length - 1; i++) {
        const [pos1, h1] = limits[i];
        const [pos2, h2] = limits[i+1];
        const dist = pos2 - pos1;
        
        maxHeight = Math.max(maxHeight, h1, h2);
        maxHeight = Math.max(maxHeight, Math.floor((h1 + h2 + dist) / 2));
    }
    
    return maxHeight;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(m log m)，其中 m 是限制条件的数量，主要是排序的时间复杂度
空间复杂度O(m)，用于存储处理后的限制条件

相关题目