大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

就是我们玩的俄罗斯方块。但只有正方形，且正方形的大小不固定。正方形的底部有粘性，只要跟已有图形有任何的重叠，就可以固定在一起。

如下图所示。

解题方法

分析

本题主要需要解决两个问题：

  1. 当每次落下来一个方块的时候，我们需要判断它会落在哪个格子的上面。
  1. 由于格子能堆叠，因此需要能知道当前格子的真实高度。

我们知道，当一个格子落到其他格子上面以后，后来的格子就只能继续向上堆。所以我们可以把已经落稳了的格子，变成长方形，且把与其有交集格子中重叠的部分覆盖了。

所以，暴力的方法很简单。

  1. 按照顺序下落格子；
  2. 找到在它下落前的格子中，与其有交集的格子；
  3. 取有交集的格子中的最大高度 + 当前格子的变长，作为此格子的高度。
  4. 把当前的格子的 [左端点，右端点，高度]保存下来。
  5. 将当前所有格子中的最大高度，保存为结果。

代码

Python 代码如下：

  1. class Solution {
  2. public:
  3.     vector<int> fallingSquares(vector<vector<int>>& positions) {
  4.         const int N = positions.size();
  5.         int maxHeight = 0;
  6.         vector<Interval> intervals;
  7.         vector<int> res;
  8.         // 遍历每个正方形
  9.         for (int i = 0; i < N; ++i) {
  10.             // 当前正方形的属性
  11.             int height = positions[i][1];
  12.             int start = positions[i][0];
  13.             int end = start + height;
  14.             // 与之前的图形交集中的最大的高度
  15.             int baseHeight = 0;
  16.             // 找之前掉落的图形中有交集的
  17.             for (Interval interval : intervals) {
  18.                 if (interval.start >= end || interval.end <= start) {
  19.                     continue;
  20.                 }
  21.                 // 交集中取最大高度
  22.                 baseHeight = max(baseHeight, interval.height);
  23.             }
  24.             // 新高度
  25.             int newHeight = height + baseHeight;
  26.             // 把当前的正方形（高度为其新高度）放入历史图形中
  27.             intervals.push_back(Interval(start, end, newHeight));
  28.             // 更新最大高度
  29.             maxHeight = max(maxHeight, newHeight);
  30.             // 更新结果
  31.             res.push_back(maxHeight);
  32.         }
  33.         return res;
  34.     }
  35. struct Interval {
  36.         int start;
  37.         int end;
  38.         int height;
  39.         Interval(int start, int end, int height) 
  40.             : start(start), end(end), height(height) {}
  41.     };
  42. };

复杂度

  • 时间复杂度：699. 掉落的方块 - 图1，699. 掉落的方块 - 图2是格子的个数。
  • 空间复杂度：699. 掉落的方块 - 图3。

总结

  1. 把问题抽象出来，代码不难写。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。