最高建筑高度

1840. 最高建筑高度

在一座城市里，你需要建 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⁹

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxBuilding(int n, vector<vector<int>>& restrictions) { } };

java 解法, 执行用时: 55 ms, 内存消耗: 78.3 MB, 提交时间: 2023-10-25 23:15:27

class Solution {
    public int maxBuilding(int n, int[][] r) {
        if (r == null || r.length == 0)   return n - 1;
        Arrays.sort(r, Comparator.comparingInt(x -> x[0]));
        int len = r.length;

        for (int i = len - 2; i >= 0; i--) {
            r[i][1] = Math.min(r[i][1], Math.min(r[i][0] - 1, r[i + 1][1] + r[i + 1][0] - r[i][0]));
        }

        int maxHeight = (0 + r[0][1] + r[0][0] - 1) >> 1;
        for (int i = 1; i <= len - 1; i++) {
            r[i][1] = Math.min(r[i][1], Math.min(r[i][0] - 1, r[i - 1][1] + r[i][0] - r[i - 1][0]));
            maxHeight = Math.max(maxHeight, (r[i - 1][1] + r[i][1] + r[i][0] - r[i - 1][0]) >> 1);
        }
        maxHeight = Math.max(maxHeight, r[len - 1][1] + n - r[len - 1][0]);
        return maxHeight;
    }
}

python3 解法, 执行用时: 536 ms, 内存消耗: 44.1 MB, 提交时间: 2023-10-25 23:15:12

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        r = restrictions
        # 增加限制 (1, 0)
        r.append([1, 0])
        r.sort()

        # 增加限制 (n, n-1)
        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):
            # 计算 r[i][0] 和 r[i][1] 之间的建筑的最大高度
            best = ((r[i + 1][0] - r[i][0]) + r[i][1] + r[i + 1][1]) // 2
            ans = max(ans, best)
        
        return ans

cpp 解法, 执行用时: 804 ms, 内存消耗: 100.5 MB, 提交时间: 2023-10-25 23:14:58

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        auto&& r = restrictions;
        // 增加限制 (1, 0)
        r.push_back({1, 0});
        sort(r.begin(), r.end());

        // 增加限制 (n, n-1)
        if (r.back()[0] != n) {
            r.push_back({n, n - 1});
        }

        int m = r.size();
        
        // 从左向右传递限制
        for (int i = 1; i < m; ++i) {
            r[i][1] = min(r[i][1], r[i - 1][1] + (r[i][0] - r[i - 1][0]));
        }
        // 从右向左传递限制
        for (int i = m - 2; i >= 0; --i) {
            r[i][1] = min(r[i][1], r[i + 1][1] + (r[i + 1][0] - r[i][0]));
        }
            
        int ans = 0;
        for (int i = 0; i < m - 1; ++i) {
            // 计算 r[i][0] 和 r[i][1] 之间的建筑的最大高度
            int best = ((r[i + 1][0] - r[i][0]) + r[i][1] + r[i + 1][1]) / 2;
            ans = max(ans, best);
        }
        
        return ans;
    }
};

上一题

下一题

详情