🎮 十亿高楼莫开阵，万点锚链定乾坤
你是一个刚拿到城市规划师资格证的新人，市长给了你一个看似简单的任务：
“小伙子，给你 n 块地，给我建一排楼。记住三条规矩：”
- 第一栋楼必须是平地（高度 0） —— “市政府的脸面，不能比隔壁穷”
- 相邻楼高度差不能超过 1 —— “市民恐高，差距太大要打架的”
- 有些地块有硬性限高令 —— “某些地段被大佬盯上了，你懂的”
目标：在不违反任何规则的前提下，让最高的楼尽可能高。
听起来很简单？呵呵，天真。n 最大能达到 10^9，你要是敢开个数组暴力模拟，内存直接 OOM 给你看，连报错信息都来不及显示就 GG 了。
naive 玩家的陷阱：
def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
# 直接开数组，炸你没商量
heights = [-1] * (n + 1)
heights[1] = 0
for idx, h in restrictions:
heights[idx] = h
# 从前往后推
for i in range(2, n + 1):
if heights[i] == -1 or heights[i] > heights[i - 1] + 1:
heights[i] = heights[i - 1] + 1
# 从后往前推
for i in range(n - 1, 0, -1):
if heights[i] > heights[i + 1] + 1:
heights[i] = heights[i + 1] + 1
return max(heights)
逻辑非常直观，开一个长度为n+1的数组，1号楼高度0，所有限高令填进去，然后：
- 从左往右扫一遍：每栋楼最多比左边高 1 层（“老王家的楼比你高一截，你不能比他高太多”）
- 从右往左扫一遍：每栋楼最多比右边高 1 层（“老李家的楼也得考虑，做人要圆滑”）
- 取最大值：完事！
思路没毛病，代码写得也挺工整，如果这是在面试的话，你已经成功拿到——“谢谢参与”！
当 n = 10^9 时，你将需要创建出一个长度为 10^9 + 1 的列表。每个整数在 Python 里大约占用 28 字节（别问为什么这么多，问就是 Python 的对象头、引用计数、类型指针一堆开销），总内存 ≈ 10^9 × 28 bytes ≈ 28 GB——28 GB！
你的电脑会经历以下心路历程：
第 1 秒： “嗯？用户要申请 28GB 内存？行吧，我看看…” 第 2 秒： “等等，系统总共才 16GB，这哥们儿疯了吧？” 第 3 秒： “不行，我得阻止这场灾难——MemoryError！滚！”
然后你的程序连个像样的报错都来不及打印，就直接被操作系统掐死了，就像游戏里刚出新手村就被满级 Boss 一巴掌拍回重生点，连复活币都来不及用。
🕳 脑洞小剧场 1： 面试官：“你这个算法的空间复杂度是多少？” 你：“O(n)… 呃，应该是线性级别？” 面试官：“那如果 n 是十亿呢？” 你：“那就… 换台内存更大的机器？实在不行上分布式？” 面试官（微笑）：“好的，今天的面试就到这里，出门右转不送。”
🕳 脑洞小剧场 2： 现实中的程序员：“我代码本地测试好好的啊，怎么一上线就崩？” 运维大哥（看着监控大屏上飙升的内存曲线）：“你这哪是写代码，你这是在挖矿吧？” Python 解释器：“兄弟，我知道你是搞算法的，但你能不能有点 B 树？我这小身板扛不住你这么造啊！”
正确的姿势：四两拨千斤
既然不能遍历所有建筑，那就只处理有限制条件的建筑！毕竟n大到十亿，但限制只有十万。而且，最重要的是，没有限制的建筑，它们的高度完全由相邻的限制点决定——就像游戏里的 NPC，行为完全由几个关键剧情点控制。你不需要模拟整个开放世界，只需要抓住主线任务的关键节点。
也就是说，只需要把有限制的位置拎出来，两两相邻之间从两端往中间爬坡，最高点就是这段区间的天际线峰值。
第一步：添加两个"隐形守护者"，把1号楼和n号楼也当成限制点加进去：第一栋楼高度为 0（[1, 0]），最后一栋楼理论上可以无限高（[n, inf]）——至少在没受到限制传导之前是这样。
第二步：按建筑编号从小到大排序，就像把NPC按出场顺序排好。
class Solution:
def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
# 第一步：加上两个"隐形锚点"
restrictions += [[1, 0], [n, inf]]
# 第二步：按建筑编号从小到大排序
restrictions.sort(key=lambda a: a[0])
# 第三步：准备两轮扫描：
m = len(restrictions)
h = [0] * m # h[i] 表示第 i 个锚点的真实最大高度
第三步：双向松弛——左右横跳直到收敛
从左往右扫第一遍。每两个相邻限制点之间隔了d栋楼，左端点高度已知，右端点有硬性上限。从左边出发，每往右一栋楼最多升1层，传过来的理论最大值是左端点高度 + d，但它还有个硬性上限卡着，所以实际高度取两者的较小值。
# 从左往右扫，传导"左边来的限制"
for i in range(1, m):
dist = restrictions[i][0] - restrictions[i-1][0]
h[i] = min(h[i-1] + dist, restrictions[i][1])
第一遍扫完还不够。从右往左再扫一遍——限制是双向传导的——每个点的高度取“右边传来的理论最大值”和“当前高度”的较小值。
# 从右往左扫，传导"右边来的限制"
for i in range(m-2, -1, -1):
dist = restrictions[i+1][0] - restrictions[i][0]
h[i] = min(h[i], h[i+1] + dist)
两轮传导下来，每个限制点的实际最大高度就定死了，确保每个点都收到了来自两侧的“最严要求”。
就像是在玩一个‘传话筒’游戏。第一轮从左往右传，每个锚点说：‘我从左边过来，最多只能到这么高’。第二轮从右往左传，每个锚点又说：‘我从右边过来，最多也只能到这么高’。两轮传完，每个锚点的真实最大高度就出来了。
这叫"动态规划的双向松弛操作"。听不懂没关系，你就理解为"左右横跳直到收敛"，类似于 Bellman-Ford 算法求最短路的思路，只不过这里是求"最高高度"。
最后一步：计算相邻限制点之间的峰值
限制点的高度全部确定之后，剩下的就是算相邻两点之间的天际线峰值。
两个限制点之间，左边高度h1，右边高度h2，距离d。从左边往上爬，从右边往上爬，两条坡道在中间某处相遇，那个顶点的高度就是(d + h1 + h2) // 2。就像在两个固定高度的塔之间搭一座拱桥，你要让桥的最高点尽可能高，但又不能让坡度太陡。这个公式就是在计算最优拱形的顶点。
遍历所有相邻限制点对，取最大的顶点高度，就是全城的天际线之巅。
# 两个锚点之间的最高高度 = (距离 + 左高 + 右高) // 2
return max(restrictions[i + 1][0] - restrictions[i][0] + h[i] + h[i + 1]
for i in range(m - 1)) // 2
时间O(m log m)，空间O(m)，只需要存储限制点，而不是所有建筑。
把十亿次操作压缩成十万次，把28GB内存压缩成几个变量——不是靠更快的机器，是靠更聪明的思路。
通关口诀：
十亿高楼莫开阵，万点锚链定乾坤。
双向传导消冲突，拱桥公式现峰值。
不要试图控制每一个细节（内存会炸），而是要抓住关键节点（限制点），让它们之间的区域自动达到最优状态。
这不就是人生吗？——你不可能掌控每一件事，但你可以抓住那些真正重要的转折点！
等等——这是什么强行升华的鸡汤转折？！打住！！
现实很骨感的，就算你抓住了人生的关键节点，你人生的内存该爆还是得爆。你老板不会因为你懂“拱桥公式”就给你涨薪，你对象也不会因为你会写“双向扫描”就不跟你分手。
所以，收起你的文艺细胞，先把今天的拱桥公式消化透。起码保证下次面试，不会再因为这题收到面试官微笑着递来的 MemoryError 好人卡。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。