企业官网建设流程全解析

这题本质是：每个方块落下时，落在它水平覆盖区间内已有最高高度上，再加上自身边长。每次落完后，还要输出当前全局最大堆叠高度。

由于 positions.length <= 1000，直接用 O(n²) 枚举模拟 就足够，面试里也更稳。

class Solution {
public List fallingSquares(int[][] positions) {
int n = positions.length;
// heights[i] 表示第 i 个方块落下后，它所在堆叠的最终高度
int[] heights = new int[n];
List ans = new ArrayList<>();
int globalMax = 0;

for (int i = 0; i < n; i++) { int left = positions[i][0]; int side = positions[i][1]; int right = left + side - 1; int base = 0; // 和之前所有方块检查是否水平重叠 for (int j = 0; j < i; j++) { int pLeft = positions[j][0]; int pSide = positions[j][1]; int pRight = pLeft + pSide - 1; // 两个区间 [left, right] 与 [pLeft, pRight] 有重叠 if (pLeft <= right && pRight >= left) { base = Math.max(base, heights[j]); } } heights[i] = base + side; globalMax = Math.max(globalMax, heights[i]); ans.add(globalMax); } return ans; }

}

关键点

• 方块覆盖区间是 [left, left + sideLength - 1]，不是左闭右开。
• 两个方块水平重叠条件：prevLeft <= right && prevRight >= left。
• 当前方块最终高度 = 重叠区间内最大已有高度 + 自身边长。
• 答案要求的是 每一步的全局最大高度，所以要用 globalMax 维护前缀最大值。

复杂度

• 时间复杂度：O(n²)
• 空间复杂度：O(n)

如果想进一步优化，可以用 离散化 + 线段树，支持区间查询最大值、区间赋值最大值，时间复杂度可以降到 O(n log n)。

要不要说说这道题的线段树优化思路？区间查询最大值和区间赋值最大值这两个操作组合起来，实现上有个细节容易踩坑。