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

LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.19
• 题目：1840. 最高建筑高度
• 难度：困难
• 标签：数组、排序、贪心

1. 题目理解

问题描述
共有编号 1~n 的一排建筑，约束规则：

1. 1号建筑高度固定为 0；
2. 相邻建筑高度差不超过 1；
3. 给定限制数组restrictions = [[id, maxHeight]]，代表编号 id 的建筑高度不能超过 maxHeight；
   求所有建筑能达到的最大高度。

示例

输入：n = 10, restrictions = [[5,3],[2,5],[7,4]]
输出：5

2. 解题思路

核心观察

1. 限制无序，必须先按建筑编号升序排序；
2. 正向遍历：从左到右修正每个限制的合法上限，左侧建筑高度最多每次+1；
3. 反向遍历：从右到左再次修正，右侧建筑高度最多每次+1；
4. 任意两个限制建筑之间，能达到的峰值高度公式：(间距 + 左高度 + 右高度) / 2；
5. 最后还要对比末尾限制到 n 号建筑的最大高度。

算法步骤

1. 无限制直接返回 n-1；
2. 将限制数组按建筑编号升序排序；
3. 正向遍历修正每个限制的合法最大高度；
4. 反向遍历再次收紧高度限制；
5. 遍历每一对相邻限制，计算区间峰值，更新全局最大值；
6. 对比第一段区间、末尾到 n 的区间高度，返回最大值。

3. 代码实现

packagelc1800_lc1899.lc1840;importjava.util.Arrays;importjava.util.Comparator;classSolution{publicintmaxBuilding(intn,int[][]restrictions){if(restrictions==null||restrictions.length==0){returnn-1;}Arrays.sort(restrictions,Comparator.comparingInt(a->a[0]));intm=restrictions.length;intprevIdx=1;intprevH=0;for(inti=0;i<m;i++){intidx=restrictions[i][0];intlimit=restrictions[i][1];intmaxCan=prevH+(idx-prevIdx);restrictions[i][1]=Math.min(limit,maxCan);prevIdx=idx;prevH=restrictions[i][1];}prevIdx=n;prevH=n-1;for(inti=m-1;i>=0;i--){intidx=restrictions[i][0];intlimit=restrictions[i][1];intmaxCan=prevH+(prevIdx-idx);restrictions[i][1]=Math.min(limit,maxCan);prevIdx=idx;prevH=restrictions[i][1];}intres=0;prevIdx=1;prevH=0;for(inti=0;i<m;i++){intcurIdx=restrictions[i][0];intcurH=restrictions[i][1];intdist=curIdx-prevIdx;intmidMax=(dist+prevH+curH)/2;res=Math.max(res,midMax);prevIdx=curIdx;prevH=curH;}res=Math.max(res,prevH+(n-prevIdx));returnres;}}

4. 代码优化说明

classSolution{publicintmaxBuilding(intn,int[][]restrictions){intm=restrictions.length;// 无限制直接返回n-1if(m==0){returnn-1;}// 按建筑编号升序排序限制条件Arrays.sort(restrictions,(a,b)->a[0]-b[0]);// h数组存储每个限制建筑修正后的合法最大高度int[]h=newint[m];// 正向遍历：从1号建筑向右收紧高度上限h[0]=Math.min(restrictions[0][0]-1,restrictions[0][1]);for(inti=1;i<m;i++){h[i]=Math.min(h[i-1]+restrictions[i][0]-restrictions[i-1][0],restrictions[i][1]);}// 反向遍历：从右向左再次收紧高度上限for(inti=m-2;i>=0;i--){h[i]=Math.min(h[i],h[i+1]+restrictions[i+1][0]-restrictions[i][0]);}// 初始化答案：第一段1到首个限制的峰值 + 最后一个限制到n的峰值intans=Math.max((restrictions[0][0]-1+h[0])/2,h[m-1]+n-restrictions[m-1][0]);// 遍历相邻限制区间，计算区间内可达到的最高峰值for(inti=0;i<m-1;i++){ans=Math.max(ans,(restrictions[i+1][0]-restrictions[i][0]+h[i]+h[i+1])/2);}returnans;}}

5. 复杂度分析

• 原始实现
  时间复杂度：O(mlog⁡m+m)O(m\log m + m)O(mlogm+m)，排序占主要耗时，多次循环操作二维数组
  空间复杂度：O(1)O(1)O(1)，原地修改限制数组，无额外容器
• 优化实现
  时间复杂度：O(mlog⁡m+m)O(m\log m + m)O(mlogm+m)，排序耗时不变，循环逻辑合并精简，减少重复下标计算
  空间复杂度：O(m)O(m)O(m)，一维数组存储高度，不修改原限制数组；减少多层临时变量与分支判断，逻辑更紧凑

6. 总结

• 核心：双向贪心修正限制高度，区间峰值公式求最大高度；
• 优化亮点：使用一维数组分离编号与高度，减少二维数组频繁访问；合并最大值初始化逻辑，删减冗余临时变量；
• 关键公式：两建筑区间峰值 = (建筑间距 + 左高度 + 右高度) // 2，是求解区间最高建筑的核心数学推导。