当前位置：首页 > news >正文

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

news 2026/6/23 19:28:24

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]]
输出：5

2. 解题思路

核心观察

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

算法步骤

无限制直接返回 n-1；
将限制数组按建筑编号升序排序；
正向遍历修正每个限制的合法最大高度；
反向遍历再次收紧高度限制；
遍历每一对相邻限制，计算区间峰值，更新全局最大值；
对比第一段区间、末尾到 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)，一维数组存储高度，不修改原限制数组；减少多层临时变量与分支判断，逻辑更紧凑