Hard

题目描述

有几个方块掉落在二维平面的 X 轴上。

给定一个二维整数数组 positions，其中 positions[i] = [lefti, sideLengthi] 表示第 i 个边长为 sideLengthi 的方块，其左边缘与 X 坐标 lefti 对齐后掉落。

每个方块按顺序从高于任何已落地方块的高度掉落。然后它向下坠落（负 Y 方向），直到落在另一个方块的顶面或 X 轴上。方块擦过另一个方块的左/右侧不算落在它上面。一旦落地，方块就会冻结在原地，无法移动。

在每个方块掉落后，你需要记录当前最高的方块堆叠的高度。

返回一个整数数组 ans，其中 ans[i] 表示第 i 个方块掉落后上述描述的高度。

示例 1：

输入：positions = [[1,2],[2,3],[6,1]]
输出：[2,5,5]
解释：
第一次掉落后，最高的堆叠是方块 1，高度为 2。
第二次掉落后，最高的堆叠是方块 1 和 2，高度为 5。
第三次掉落后，最高的堆叠仍是方块 1 和 2，高度为 5。
因此返回 [2, 5, 5]。

示例 2：

输入：positions = [[100,100],[200,100]]
输出：[100,100]
解释：
第一次掉落后，最高的堆叠是方块 1，高度为 100。
第二次掉落后，最高的堆叠是方块 1 或方块 2，都是高度 100。
因此返回 [100, 100]。
注意方块 2 只是擦过方块 1 的右侧，这不算落在它上面。

约束条件：

  • 1 <= positions.length <= 1000
  • 1 <= lefti <= 10^8
  • 1 <= sideLengthi <= 10^6

解题思路

这道题的核心是模拟方块下降过程，需要维护每个位置的高度信息。

思路分析：

  1. 暴力模拟法：对于每个掉落的方块，遍历之前所有的方块，找出与当前方块在 X 轴上有重叠的方块，取最高的高度作为当前方块的底部高度。

  2. 坐标压缩 + 线段树：由于坐标范围很大（最大 10^8），直接建立数组会超内存。可以使用坐标压缩，将所有可能的坐标映射到较小的范围，然后用线段树维护区间最大值。

  3. 有序集合优化：维护已放置方块的信息，对于新方块，只需检查与其有重叠的方块。

推荐解法：暴力模拟

由于 n ≤ 1000，暴力模拟的时间复杂度 O(n²) 是可以接受的。对于每个新方块：

  • 计算其左右边界 [left, right)
  • 遍历之前的所有方块，找出与当前方块有重叠的方块
  • 在这些重叠方块中找到最高的高度
  • 当前方块的高度 = 最高重叠高度 + 当前方块边长
  • 更新全局最大高度

两个方块重叠的条件：方块1的区间 [a, b) 和方块2的区间 [c, d) 重叠当且仅当 max(a,c) < min(b,d)。

代码实现

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        vector<int> result;
        vector<vector<int>> squares; // [left, right, height]
        int maxHeight = 0;
        
        for (auto& pos : positions) {
            int left = pos[0];
            int side = pos[1];
            int right = left + side;
            
            int baseHeight = 0;
            // 找到与当前方块重叠的所有方块中的最大高度
            for (auto& square : squares) {
                int sLeft = square[0], sRight = square[1], sHeight = square[2];
                // 检查是否重叠：max(left, sLeft) < min(right, sRight)
                if (max(left, sLeft) < min(right, sRight)) {
                    baseHeight = max(baseHeight, sHeight);
                }
            }
            
            int newHeight = baseHeight + side;
            squares.push_back({left, right, newHeight});
            maxHeight = max(maxHeight, newHeight);
            result.push_back(maxHeight);
        }
        
        return result;
    }
};

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        result = []
        squares = []  # [left, right, height]
        max_height = 0
        
        for left, side in positions:
            right = left + side
            
            base_height = 0
            # 找到与当前方块重叠的所有方块中的最大高度
            for s_left, s_right, s_height in squares:
                # 检查是否重叠
                if max(left, s_left) < min(right, s_right):
                    base_height = max(base_height, s_height)
            
            new_height = base_height + side
            squares.append([left, right, new_height])
            max_height = max(max_height, new_height)
            result.append(max_height)
        
        return result

public class Solution {
    public IList<int> FallingSquares(int[][] positions) {
        var result = new List<int>();
        var squares = new List<int[]>(); // [left, right, height]
        int maxHeight = 0;
        
        foreach (var pos in positions) {
            int left = pos[0];
            int side = pos[1];
            int right = left + side;
            
            int baseHeight = 0;
            // 找到与当前方块重叠的所有方块中的最大高度
            foreach (var square in squares) {
                int sLeft = square[0], sRight = square[1], sHeight = square[2];
                // 检查是否重叠
                if (Math.Max(left, sLeft) < Math.Min(right, sRight)) {
                    baseHeight = Math.Max(baseHeight, sHeight);
                }
            }
            
            int newHeight = baseHeight + side;
            squares.Add(new int[]{left, right, newHeight});
            maxHeight = Math.Max(maxHeight, newHeight);
            result.Add(maxHeight);
        }
        
        return result;
    }
}

var fallingSquares = function(positions) {
    const result = [];
    const squares = []; // [left, right, height]
    let maxHeight = 0;
    
    for (const [left, side] of positions) {
        const right = left + side;
        
        let baseHeight = 0;
        // 找到与当前方块重叠的所有方块中的最大高度
        for (const [sLeft, sRight, sHeight] of squares) {
            // 检查是否重叠
            if (Math.max(left, sLeft) < Math.min(right, sRight)) {
                baseHeight = Math.max(baseHeight, sHeight);
            }
        }
        
        const newHeight = baseHeight + side;
        squares.push([left, right, newHeight]);
        maxHeight = Math.max(maxHeight, newHeight);
        result.push(maxHeight);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)对于每个方块，需要检查之前的所有方块
空间复杂度O(n)存储所有方块的信息

相关题目