LeetCode解析——699.掉落的方块数据结构与算法weixin44337475的博客-

题目：

在无限长的数轴（即 x 轴）上，我们根据给定的顺序放置对应的正方形方块。
第 i 个掉落的方块（positions[i] = (left, side_length)）是正方形，其中 left 表示该方块最左边的点位置(positions[i][0])，side_length
表示该方块的边长(positions[i][1])。 每个方块的底部边缘平行于数轴（即 x轴），并且从一个比目前所有的落地方块更高的高度掉落而下。在上一个方块结束掉落，并保持静止后，才开始掉落新方块。
方块的底边具有非常大的粘性，并将保持固定在它们所接触的任何长度表面上（无论是数轴还是其他方块）。邻接掉落的边不会过早地粘合在一起，因为只有底边才具有粘性。
返回一个堆叠高度列表 ans 。每一个堆叠高度 ans[i] 表示在通过 positions[0], positions[1], …,
positions[i] 表示的方块掉落结束后，目前所有已经落稳的方块堆叠的最高高度。

示例1：

输入: [[1, 2], [2, 3], [6, 1]] 输出: [2, 5, 5] 解释: 第一个方块 positions[0] =
[1, 2] 掉落：
_aa
_aa
——- 方块最大高度为 2 。 第二个方块 positions[1] = [2, 3] 掉落：
__aaa
__aaa
aaa
aa
aa
————– 方块最大高度为5。 大的方块保持在较小的方块的顶部，不论它的重心在哪里，因为方块的底部边缘有非常大的粘性。 第三个方块 positions[1] = [6, 1] 掉落：
__aaa
__aaa
__aaa
_aa
_aa___a
————– 方块最大高度为5。 因此，我们返回结果[2, 5, 5]。

示例2：

输入: [[100, 100], [200, 100]] 输出: [100, 100]
解释:
相邻的方块不会过早地卡住，只有它们的底部边缘才能粘在表面上。

简单介绍：
题目：掉落的方块
题目难度：困难
使用语言：JAVA。
这道题来自leetcode题库的Ordered Map标签。
如果想要加深对java拥有数据结构类型的理解，特别是Map的理解，做这类型的题是提升很快的。

解题思路：
首先看题、分析题意，我们可以明确2个关键点：
1.掉落方块后，该区间的最大高度，也叫当前最大高度。
2.掉落方块后，所有区间的最大高度，也叫最大高度。
既然，我们已经分析出来题目的关键任务了，下面我们就可以开始思考实现了。
我们采用算法与数据结构的思路来剖析一下这题，

数据结构：
要实现对数据的操作，我们要先明确存储数据的数据结构。
该题的数据结构的作用，是保存最大高度和当前最大高度。
我们采用了2个顺序表：
List hList：来保存当前最大高度，
List list：保存最大高度。

算法：
既然明确了hList和list作为解决该题的数据结构，我们就可以开始我们的算法分析了。
1.模拟掉落的方块（0<=i<=positions.length）
2.添加当前区间最大高度。先判断当前方块是否可以放在之前的方块上方，并取得最高值
3.添加完当前最大高度，再找到目前所有区间的最大高度。

代码部分：

import java.util.*; public class Solution { public List<Integer> fallingSquares(int [][] positions){   List<Integer> hList=new ArrayList<>();//存放当前方块高度   List<Integer> list=new ArrayList<>();//存放最大高度 if(positions.length==0||positions==null) {//没有掉落的方块，返回当前最大高度顺序表 return list; } int high=positions[0][1];//初始化当前高度 int maxH=positions[0][1];//初始化最大高度   hList.add(high);   list.add(maxH); for(int i=1;i<positions.length;i++) {    high=positions[i][1]; //判断当前方块是否可以放在之前的方块上方，并取得最高值 for(int j=i-1;j>=0;j--) { if(!(positions[j][0]>=positions[i][0]+positions[i][1]||       positions[j][0]+positions[j][1]<=positions[i][0])) { int temp;//临时高度      temp=hList.get(j)+positions[i][1];//当前区间高度 if(temp>high) {       high=temp; } } }    hList.add(high); if(high>maxH) {     maxH=high; }    list.add(maxH); } return list; } } 

结语：
晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！