1840.最高建筑高度：左右两次扫描，传递限制约束(没有很多头痛公式版)

【LetMeFly】1840.最高建筑高度：左右两次扫描，传递限制约束(没有很多头痛公式版)

力扣题目链接：https://leetcode.cn/problems/maximum-building-height/

在一座城市里，你需要建 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 <= 109
• 0 <= restrictions.length <= min(n - 1, 105)
• 2 <= idi <= n
• idi 是 唯一的 。
• 0 <= maxHeighti <= 109

解题方法：从左到右限制一次 + 从右到左限制一次

假设能确定坐标$a$的楼可以达到$ha$这么高，其右边坐标$b$的楼可以达到$hb$这么高，那么从$a$到$b$这段区间的楼最多能有多高呢？

不妨假设$ha\leq hb$，那么楼高总体上呈现先上升后下降的趋势。$a$处楼高$ha$，$a+1$处楼高$ha+1$，…，$a + (hb-ha)$处楼高$hb$（和$b$处等高）。

$a + (hb-ha)$处和$b$处楼都高$hb$，如果二者之间有一栋或两栋楼则最高高度可达$hb+1$，如果二者之间有三栋或四栋楼则最高高度可达$hb+2$，…，如果二者之间有$n$栋楼则最高高度可达$hb+\lfloor\frac{n+1}{2}\rfloor$。由于二者之间有$b-a-(hb-ha)-1$栋楼所以二者之间最高高度可达$hb+\lfloor\frac{b-a-(hb-ha)}{2}\rfloor$，即为从$a$到$b$这段范围的最大楼高。

如果$ha\gt hb$同理，不妨直接交换$ha$和$hb$使得$ha\lt hb$，这样并不影响这段区间的最大楼高计算结果。

现在问题是每个关键坐标的最大楼高确定了吗？还没有。

前面讨论的前提是坐标$a$的楼可以达到$ha$这么高，而题目中给的$maxHeight$限制不一定能达到！

例如假设坐标$5$的楼最高为$3$，那么坐标$7$的楼最高为$5$，即使题目中给$restrictions[i]=[7, 99999]$的限制也达不到。

最终剩下了如何确定每个关键点的最大高度这一个关键问题了，很简单：

一个楼的最大高度限制除了题目给定的自身限制以外，还有来自其左右楼高的限制。

我们从左到右遍历一遍关键坐标的楼高并传递更新最大楼高限制，再从右往左遍历一遍传递更新最大楼高限制，不就ok了吗？

假设坐标$a$的楼高限制是$ha$，那么其右边坐标$b$的楼高最多为$ha+b-a$。

注意题目中还有两个初始情况下的额外限制：坐标$1$最大高度$0$，坐标$n$最大高度$+\infty$。

时空复杂度分析：

• 时间复杂度$O(m\log m)$，其中$m=len(restrictions)$，$\log m$的时间复杂度来自排序；
• 空间复杂度$O(\log m)$。

AC代码

C++

/*
 * @LastEditTime: 2026-06-20 11:17:44
 */
/*
从左到右限制一遍再从右到左限制一遍是不是就可以了呢？是不是不需要由较低的高度往两边限制呢？
*/
class Solution {
private:
    int cal(int a, int ha, int b, int hb) {
        if (ha > hb) {
            swap(ha, hb);
        }
        return hb + (b - a - (hb - ha)) / 2;
    }
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        restrictions.push_back({1, 0});
        restrictions.push_back({n, INT_MAX});
        sort(restrictions.begin(), restrictions.end());
        for (int i = 1; i < restrictions.size(); i++) {
            restrictions[i][1] = min(restrictions[i][1], restrictions[i - 1][1] + restrictions[i][0] - restrictions[i - 1][0]);
        }
        for (int i = restrictions.size() - 2; i >= 0; i--) {
            restrictions[i][1] = min(restrictions[i][1], restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0]);
        }
        
        int ans = 0;
        for (int i = 1; i < restrictions.size(); i++) {
            ans = max(ans, cal(restrictions[i - 1][0], restrictions[i - 1][1], restrictions[i][0], restrictions[i][1]));
        }
        return ans;
    }

    void testCal() {
        assert(cal(7, 3, 10, 4) == 5);
        assert(cal(7, 4, 10, 3) == 5);
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源