这是一道经典的贪心算法结合双向遍历的题目。这道题的核心难点在于某个建筑的限制不仅取决于它自身的 restrictions还受到左右两侧建筑高度差不能超过 1 的约束。这意味着一个位置的限制会“传递”给相邻的位置。核心思路1. 预处理与排序* 题目给的限制是离散的我们需要先将其排序。* 关键点必须把起始点 (1, 0) 加入限制列表因为题目规定第1栋楼高度必须是0。同时为了方便处理边界可以将终点 (n, n-1) 也加入因为从1走到n最高也就是 n-1。2. 双向传递限制修正限制* 从左向右如果左边的楼高度是 h距离是 d那么当前楼最高只能是 h d。如果原限制比这个大说明原限制达不到需要缩小。* 从右向左同理右边的楼也会限制左边的楼。* 经过这两轮遍历restrictions 数组里的每个高度就变成了在该位置实际能达到的最大高度。3. 计算区间最大值* 在两个受限建筑 i 和 j 之间位置分别为 pos1, pos2高度分别为 h1, h2我们要找中间能达到的最高点。* 这就像是在两个山峰之间填土最高点通常出现在“爬坡”和“下坡”的交汇处。* 公式推导假设最高点为 H它距离 pos1 为 x距离 pos2 为 y。则 H h1 x 且 H h2 y同时 x y pos2 - pos1。* 解得最大高度为 (h1 h2 (pos2 - pos1)) / 2。Java 代码实现import java.util.Arrays;class Solution {public int maxBuilding(int n, int[][] restrictions) {// 1. 数据预处理// 将 restrictions 转换为 List 方便操作或者新建一个数组// 我们需要加入 (1, 0) 这个硬性限制int[][] arr;if (restrictions.length 0 || restrictions[0][0] ! 1) {arr new int[restrictions.length 1][2];arr[0] new int[]{1, 0}; // 加入起始点限制System.arraycopy(restrictions, 0, arr, 1, restrictions.length);} else {// 如果题目数据里已经包含了1虽然题目说不会但为了健壮性arr restrictions;}// 按位置排序Arrays.sort(arr, (a, b) - a[0] - b[0]);// 2. 从左向右遍历传递限制// 当前建筑的高度不能超过前一栋建筑高度 距离for (int i 1; i 0; i--) {int dist arr[i 1][0] - arr[i][0];arr[i][1] Math.min(arr[i][1], arr[i 1][1] dist);}int maxH 0;// 4. 计算每两个限制点之间的最大高度for (int i 0; i H (h1 h2 dist) / 2int peak (h1 h2 dist) / 2;maxH Math.max(maxH, peak);}// 5. 处理最后一个限制点到 n 的情况// 如果最后一个限制点不是 n我们需要计算从最后一个限制点爬到 n 的最大高度int lastPos arr[arr.length - 1][0];int lastH arr[arr.length - 1][1];if (lastPos 右:* i1: 位置2距离1。min(1, 01) 1。不变。* i2: 位置4距离2。min(1, 12) 1。不变。* 右-左:* i1: 位置2距离2。min(1, 12) 1。不变。* i0: 位置1距离1。min(0, 11) 0。不变。* 计算区间:* 区间 [1,0] 到 [2,1]: (011)/2 1。* 区间 [2,1] 到 [4,1]: (112)/2 2。 (最大值)* 尾部: 从位置4(高度1)到位置5。1 (5-4) 2。* 结果: 2。