最高建筑高度
难度:
标签:
题目描述
在一座城市里，你需要建 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 <= 1090 <= restrictions.length <= min(n - 1, 105)2 <= idi <= nidi是 唯一的 。0 <= maxHeighti <= 109
代码结果
运行时间: 206 ms, 内存: 43.3 MB
/*
* 思路：
* 1. 首先将restrictions数组按照建筑的编号进行排序，并在restrictions数组的头部和尾部添加边界条件[1, 0]和[n, n-1]。
* 2. 然后从左向右遍历restrictions数组，确保每个限制高度满足相邻建筑高度差不能超过1的条件。
* 3. 再从右向左遍历restrictions数组，确保每个限制高度满足相邻建筑高度差不能超过1的条件。
* 4. 最后遍历每两个相邻的限制，计算可以达到的最高高度。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int maxBuilding(int n, int[][] restrictions) {
if (restrictions.length == 0) return n - 1;
List<int[]> list = new ArrayList<>();
list.add(new int[]{1, 0});
list.addAll(Arrays.stream(restrictions).sorted(Comparator.comparingInt(a -> a[0])).collect(Collectors.toList()));
list.add(new int[]{n, n - 1});
for (int i = 1; i < list.size(); i++) {
list.get(i)[1] = Math.min(list.get(i)[1], list.get(i - 1)[1] + list.get(i)[0] - list.get(i - 1)[0]);
}
for (int i = list.size() - 2; i >= 0; i--) {
list.get(i)[1] = Math.min(list.get(i)[1], list.get(i + 1)[1] + list.get(i + 1)[0] - list.get(i)[0]);
}
return IntStream.range(1, list.size())
.map(i -> {
int[] prev = list.get(i - 1);
int[] curr = list.get(i);
int dist = curr[0] - prev[0];
return (dist + prev[1] + curr[1]) / 2;
})
.max()
.orElse(0);
}
}解释
方法:
此题解采用了从左至右和从右至左两次扫描的方法来处理建筑的高度限制。首先，按照建筑编号对限制进行排序。然后，从右向左对限制进行一次扫描，以确保每个建筑的高度限制不会因为右侧建筑的高度限制而变得不可能。在这个过程中，每个建筑的最大高度会根据其右侧建筑的最大高度和两建筑间的距离进行调整。接着，从左至右遍历所有建筑，利用当前建筑的高度和下一个受限制建筑的高度以及两者之间的距离来逐步确定每个建筑的实际高度，并计算可能的最大高度。最终，包括最后一个建筑到第n个建筑的高度差也被考虑在内。
时间复杂度:
O(r log r)
空间复杂度:
O(r)
代码细节讲解
🦆
在题解中，为什么首先需要对限制按建筑编号进行排序？
▷🦆
在从右向左更新高度限制的过程中，公式`restrictions[ri][1] = min(restrictions[ri][1], restrictions[ri+1][1] + j - i)`的具体逻辑是什么？
▷🦆
为什么在从左向右计算每个建筑的高度时，会根据条件`if hh - h >= j - i`来决定是否使用中点高度？
▷