列表

详情

699. 掉落的方块

在二维平面上的 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 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。
第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。
第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。
因此，返回 [2, 5, 5] 作为答案。

示例 2：

输入：positions = [[100,100],[200,100]]
输出：[100,100]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 100 。
第 2 个方块掉落后，最高的堆叠可以由方块 1 组成也可以由方块 2 组成，堆叠的最高高度为 100 。
因此，返回 [100, 100] 作为答案。
注意，方块 2 擦过方块 1 的右侧边，但不会算作在方块 1 上着陆。

 

提示：

相似题目

天际线问题

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> fallingSquares(vector<vector<int>>& positions) { } };

python3 解法, 执行用时: 425 ms, 内存消耗: 16.8 MB, 提交时间: 2024-07-28 11:41:33 

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        n = len(positions)
        heights = [0] * n
        for i, (left1, side1) in enumerate(positions):
            right1 = left1 + side1 - 1
            heights[i] = side1
            for j in range(i):
                left2, right2 = positions[j][0], positions[j][0] + positions[j][1] - 1
                if right1 >= left2 and right2 >= left1:
                    heights[i] = max(heights[i], heights[j] + side1)
        for i in range(1, n):
            heights[i] = max(heights[i], heights[i - 1])
        return heights

golang 解法, 执行用时: 48 ms, 内存消耗: 6.6 MB, 提交时间: 2023-06-09 15:46:14 

type SegmentNode struct {
    Ls, Rs *SegmentNode
    Val, Add int
}

func (node *SegmentNode) update(lc int, rc int, l int, r int, v int) {
    if l <= lc && rc <= r {
        node.Val, node.Add = v, v
        return
    }
    node.pushdown()
    mid := (lc + rc) >> 1
    if l <= mid {
        node.Ls.update(lc, mid, l, r, v)
    }
    if r > mid {
        node.Rs.update(mid + 1, rc, l, r, v)
    }
    node.pushup()
}

func (node *SegmentNode) query(lc int, rc int, l int, r int) (ans int) {
    if l <= lc && rc <= r {
        return node.Val
    }
    node.pushdown()
    mid := (lc + rc) >> 1
    if l <= mid {
        ans = node.Ls.query(lc, mid, l, r)
    }
    if r > mid {
        ans = max(ans, node.Rs.query(mid + 1, rc, l, r))
    }
    return
}

func (node *SegmentNode) pushup() {
    node.Val = max(node.Ls.Val, node.Rs.Val)
}

func (node *SegmentNode) pushdown() {
    if node.Ls == nil {
        node.Ls = &SegmentNode{nil, nil, 0, 0}
    }
    if node.Rs == nil {
        node.Rs = &SegmentNode{nil, nil, 0, 0}
    }
    if node.Add == 0 {
        return
    }
    node.Ls.Val, node.Ls.Add, node.Rs.Val, node.Rs.Add = node.Add, node.Add, node.Add, node.Add
    node.Add = 0
}

func fallingSquares(positions [][]int) (ans []int) {
    root, MAX_RANGE := &SegmentNode{nil, nil, 0, 0}, 1_000_000_000
    for _, pos := range positions {
        left, right := pos[0], pos[0] + pos[1] - 1
        cur := root.query(0, MAX_RANGE, left, right)
        root.update(0, MAX_RANGE, left, right, cur + pos[1])
        ans = append(ans, root.Val)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

python3 解法, 执行用时: 892 ms, 内存消耗: 25.2 MB, 提交时间: 2023-06-09 15:45:54 

# 动态开点线段树
class Node:
    def __init__(self) -> None:
        self.ls = self.rs = None
        self.val = self.add = 0

class SegmentTree:
    def __init__(self):
        self.root = Node()
    
    @staticmethod
    def update(node: Node, lc: int, rc: int, l: int, r: int, v: int) -> None:
        if l <= lc and rc <= r:
            node.add = v
            node.val = v
            return
        SegmentTree.pushdown(node)
        mid = (lc + rc) >> 1
        if l <= mid:
            SegmentTree.update(node.ls, lc, mid, l, r, v)
        if r > mid:
            SegmentTree.update(node.rs, mid + 1, rc, l, r, v)
        SegmentTree.pushup(node)
 
    @staticmethod
    def query(node: Node, lc: int, rc: int, l: int, r: int) -> int:
        if l <= lc and rc <= r:
            return node.val
        # 先确保所有关联的懒标记下沉下去
        SegmentTree.pushdown(node)
        mid, ans = (lc + rc) >> 1, 0
        if l <= mid:
            ans = SegmentTree.query(node.ls, lc, mid, l, r)
        if r > mid:
            # 同样为不同题目中的更新方式
            ans = max(ans, SegmentTree.query(node.rs, mid + 1, rc, l, r))
        return ans
    
    @staticmethod
    def pushdown(node: Node) -> None:
        # 懒标记, 在需要的时候才开拓节点和赋值
        if node.ls is None:
            node.ls = Node()
        if node.rs is None:
            node.rs = Node()
        if not node.add:
            return
        node.ls.add, node.rs.add, node.ls.val, node.rs.val = [node.add] * 4
        node.add = 0
    
    @staticmethod
    def pushup(node: Node) -> None:
        # 动态更新方式：此处为最大值
        node.val = max(node.ls.val, node.rs.val)

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        ans, st, max_range = [], SegmentTree(), int(1e9)
        for a, length in positions:
            SegmentTree.update(st.root, 0, max_range, a, a + length - 1, SegmentTree.query(st.root, 0, max_range, a, a + length - 1) + length)
            ans.append(st.root.val)
        return ans

java 解法, 执行用时: 79 ms, 内存消耗: 43.3 MB, 提交时间: 2023-06-09 15:44:52 

class Solution {
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length;
        List<Integer> ret = new ArrayList<Integer>();
        TreeMap<Integer, Integer> heightMap = new TreeMap<Integer, Integer>();
        heightMap.put(0, 0); // 初始时从 0 开始的所有点的堆叠高度都是 0
        for (int i = 0; i < n; i++) {
            int size = positions[i][1];
            int left = positions[i][0], right = positions[i][0] + positions[i][1] - 1;
            Integer lp = heightMap.higherKey(left), rp = heightMap.higherKey(right);
            Integer prevRightKey = rp != null ? heightMap.lowerKey(rp) : heightMap.lastKey();
            int rHeight = prevRightKey != null ? heightMap.get(prevRightKey) : 0; // 记录 right + 1 对应的堆叠高度（如果 right + 1 不在 heightMap 中）

            // 更新第 i 个掉落的方块的堆叠高度
            int height = 0;
            Integer prevLeftKey = lp != null ? heightMap.lowerKey(lp) : heightMap.lastKey();
            Map<Integer, Integer> tail = prevLeftKey != null ? heightMap.tailMap(prevLeftKey) : heightMap;
            for (Map.Entry<Integer, Integer> entry : tail.entrySet()) {
                if (entry.getKey() == rp) {
                    break;
                }
                height = Math.max(height, entry.getValue() + size);
            }

            // 清除 heightMap 中位于 (left, right] 内的点
            Set<Integer> keySet = new TreeSet<Integer>(tail.keySet());
            for (Integer tmp : keySet) {
                if (lp == null || tmp < lp) {
                    continue;
                }
                if (rp != null && tmp >= rp) {
                    break;
                }
                heightMap.remove(tmp);
            }

            heightMap.put(left, height); // 更新 left 的变化
            if (rp == null || rp != right + 1) { // 如果 right + 1 不在 heightMap 中，更新 right + 1 的变化
                heightMap.put(right + 1, rHeight);
            }
            ret.add(i > 0 ? Math.max(ret.get(i - 1), height) : height);
        }
        return ret;
    }
}

cpp 解法, 执行用时: 16 ms, 内存消耗: 12.1 MB, 提交时间: 2023-06-09 15:44:18 

// 有序集合
class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size();
        vector<int> ret(n);
        map<int, int> heightMap;
        heightMap[0] = 0; // 初始时从 0 开始的所有点的堆叠高度都是 0
        for (int i = 0; i < n; i++) {
            int size = positions[i][1];
            int left = positions[i][0], right = positions[i][0] + positions[i][1] - 1;
            auto lp = heightMap.upper_bound(left), rp = heightMap.upper_bound(right);
            int rHeight = prev(rp)->second; // 记录 right + 1 对应的堆叠高度（如果 right + 1 不在 heightMap 中）

            // 更新第 i 个掉落的方块的堆叠高度
            int height = 0;
            for (auto p = prev(lp); p != rp; p++) {
                height = max(height, p->second + size);
            }

            // 清除 heightMap 中位于 (left, right] 内的点
            heightMap.erase(lp, rp);

            heightMap[left] = height; // 更新 left 的变化
            if (rp == heightMap.end() || rp->first != right + 1) { // 如果 right + 1 不在 heightMap 中，更新 right + 1 的变化
                heightMap[right + 1] = rHeight;
            }
            ret[i] = i > 0 ? max(ret[i - 1], height) : height;
        }
        return ret;
    }
};

java 解法, 执行用时: 19 ms, 内存消耗: 42.8 MB, 提交时间: 2023-06-09 15:43:56 

class Solution {
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length;
        List<Integer> heights = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            int left1 = positions[i][0], right1 = positions[i][0] + positions[i][1] - 1;
            int height = positions[i][1];
            for (int j = 0; j < i; j++) {
                int left2 = positions[j][0], right2 = positions[j][0] + positions[j][1] - 1;
                if (right1 >= left2 && right2 >= left1) {
                    height = Math.max(height, heights.get(j) + positions[i][1]);
                }
            }
            heights.add(height);
        }
        for (int i = 1; i < n; i++) {
            heights.set(i, Math.max(heights.get(i), heights.get(i - 1)));
        }
        return heights;
    }
}

golang 解法, 执行用时: 24 ms, 内存消耗: 4.7 MB, 提交时间: 2023-06-09 15:43:42 

func fallingSquares(positions [][]int) []int {
    n := len(positions)
    heights := make([]int, n)
    for i, p := range positions {
        left1, right1 := p[0], p[0]+p[1]-1
        heights[i] = p[1]
        for j, q := range positions[:i] {
            left2, right2 := q[0], q[0]+q[1]-1
            if right1 >= left2 && right2 >= left1 {
                heights[i] = max(heights[i], heights[j]+p[1])
            }
        }
    }
    for i := 1; i < n; i++ {
        heights[i] = max(heights[i], heights[i-1])
    }
    return heights
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

python3 解法, 执行用时: 704 ms, 内存消耗: 16.5 MB, 提交时间: 2023-06-09 15:43:27 

# 暴力枚举
class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        n = len(positions)
        heights = [0] * n
        for i, (left1, side1) in enumerate(positions):
            right1 = left1 + side1 - 1
            heights[i] = side1
            for j in range(i):
                left2, right2 = positions[j][0], positions[j][0] + positions[j][1] - 1
                if right1 >= left2 and right2 >= left1:
                    heights[i] = max(heights[i], heights[j] + side1)
        for i in range(1, n):
            heights[i] = max(heights[i], heights[i - 1])
        return heights

上一题

© 2024 leetcode.cn