LeetCode 每日一题笔记 日期：2026.06.19 题目：1840. 最高建筑高度

LeetCode 每日一题笔记0. 前言日期2026.06.19题目1840. 最高建筑高度难度困难标签数组、排序、贪心1. 题目理解问题描述共有编号 1~n 的一排建筑约束规则1号建筑高度固定为 0相邻建筑高度差不超过 1给定限制数组restrictions [[id, maxHeight]]代表编号 id 的建筑高度不能超过 maxHeight求所有建筑能达到的最大高度。示例输入n 10, restrictions [[5,3],[2,5],[7,4]]输出52. 解题思路核心观察限制无序必须先按建筑编号升序排序正向遍历从左到右修正每个限制的合法上限左侧建筑高度最多每次1反向遍历从右到左再次修正右侧建筑高度最多每次1任意两个限制建筑之间能达到的峰值高度公式(间距 左高度 右高度) / 2最后还要对比末尾限制到 n 号建筑的最大高度。算法步骤无限制直接返回 n-1将限制数组按建筑编号升序排序正向遍历修正每个限制的合法最大高度反向遍历再次收紧高度限制遍历每一对相邻限制计算区间峰值更新全局最大值对比第一段区间、末尾到 n 的区间高度返回最大值。3. 代码实现packagelc1800_lc1899.lc1840;importjava.util.Arrays;importjava.util.Comparator;classSolution{publicintmaxBuilding(intn,int[][]restrictions){if(restrictionsnull||restrictions.length0){returnn-1;}Arrays.sort(restrictions,Comparator.comparingInt(a-a[0]));intmrestrictions.length;intprevIdx1;intprevH0;for(inti0;im;i){intidxrestrictions[i][0];intlimitrestrictions[i][1];intmaxCanprevH(idx-prevIdx);restrictions[i][1]Math.min(limit,maxCan);prevIdxidx;prevHrestrictions[i][1];}prevIdxn;prevHn-1;for(intim-1;i0;i--){intidxrestrictions[i][0];intlimitrestrictions[i][1];intmaxCanprevH(prevIdx-idx);restrictions[i][1]Math.min(limit,maxCan);prevIdxidx;prevHrestrictions[i][1];}intres0;prevIdx1;prevH0;for(inti0;im;i){intcurIdxrestrictions[i][0];intcurHrestrictions[i][1];intdistcurIdx-prevIdx;intmidMax(distprevHcurH)/2;resMath.max(res,midMax);prevIdxcurIdx;prevHcurH;}resMath.max(res,prevH(n-prevIdx));returnres;}}4. 代码优化说明classSolution{publicintmaxBuilding(intn,int[][]restrictions){intmrestrictions.length;// 无限制直接返回n-1if(m0){returnn-1;}// 按建筑编号升序排序限制条件Arrays.sort(restrictions,(a,b)-a[0]-b[0]);// h数组存储每个限制建筑修正后的合法最大高度int[]hnewint[m];// 正向遍历从1号建筑向右收紧高度上限h[0]Math.min(restrictions[0][0]-1,restrictions[0][1]);for(inti1;im;i){h[i]Math.min(h[i-1]restrictions[i][0]-restrictions[i-1][0],restrictions[i][1]);}// 反向遍历从右向左再次收紧高度上限for(intim-2;i0;i--){h[i]Math.min(h[i],h[i1]restrictions[i1][0]-restrictions[i][0]);}// 初始化答案第一段1到首个限制的峰值 最后一个限制到n的峰值intansMath.max((restrictions[0][0]-1h[0])/2,h[m-1]n-restrictions[m-1][0]);// 遍历相邻限制区间计算区间内可达到的最高峰值for(inti0;im-1;i){ansMath.max(ans,(restrictions[i1][0]-restrictions[i][0]h[i]h[i1])/2);}returnans;}}5. 复杂度分析原始实现时间复杂度O(mlog⁡mm)O(m\log m m)O(mlogmm)排序占主要耗时多次循环操作二维数组空间复杂度O(1)O(1)O(1)原地修改限制数组无额外容器优化实现时间复杂度O(mlog⁡mm)O(m\log m m)O(mlogmm)排序耗时不变循环逻辑合并精简减少重复下标计算空间复杂度O(m)O(m)O(m)一维数组存储高度不修改原限制数组减少多层临时变量与分支判断逻辑更紧凑6. 总结核心双向贪心修正限制高度区间峰值公式求最大高度优化亮点使用一维数组分离编号与高度减少二维数组频繁访问合并最大值初始化逻辑删减冗余临时变量关键公式两建筑区间峰值 (建筑间距 左高度 右高度) // 2是求解区间最高建筑的核心数学推导。