JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-09-28
目录

掉落的方块Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

在二维平面上的 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 上着陆。

提示:

  • 1 <= positions.length <= 1000
  • 1 <= lefti <= 108
  • 1 <= sideLengthi <= 106

# 思路

能够影响当前块高度的只能是已经放过的块。

所以用一个map记录已放过的块的高度,然后暴力地拿当前块和之前放过的块比较有没有重合部分,来获得当前块的最大高度

# 解法


class Solution {
    // 能够影响当前块高度的只能是已经放过的块。所以用一个map记录已放过的块的高度,然后暴力地拿当前块和之前放过的块比较有没有重合部分,来获得当前块的最大高度
    public List<Integer> fallingSquares(int[][] positions) {
        List<Integer> ans = new ArrayList<>();
        Map<Integer,Integer> records = new HashMap<>();
        int n = positions.length;
        int length;
        int left;
        int right;
        int max = 0;
        for(int i = 0 ; i < n ; i++){
            length = 0;
            left = positions[i][0];
            right = positions[i][1]+left;
            for(int j =0 ; j < i ; j++){
                if(right <= positions[j][0] || positions[j][0]+positions[j][1] <= left){
                    continue;
                }
                length = Math.max(records.get(j),length);
            }
            length += positions[i][1];
            max = Math.max(max,length);
            ans.add(max);
            records.put(i,length);
        }
        return ans;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1637. 两点之间不包含任何点的最宽垂直区域 Java
06-26
02
1636. 按照频率将数组升序排序 Java
06-26
03
1638. 统计只差一个字符的子串数目 Java
06-26
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式