0699. Falling Squares

# 699. Falling Squares#

## 题目 #

On an infinite number line (x-axis), we drop given squares in the order they are given.

The `i`-th square dropped (`positions[i] = (left, side_length)`) is a square with the left-most point being `positions[i][0]` and sidelength `positions[i][1]`.

The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next.

The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.

Return a list `ans` of heights. Each height `ans[i]` represents the current highest height of any square we have dropped, after dropping squares represented by `positions[0], positions[1], ..., positions[i]`.

Example 1:

``````Input: [[1, 2], [2, 3], [6, 1]]
Output: [2, 5, 5]
Explanation:
``````

After the first drop of `positions[0] = [1, 2]: _aa _aa -------` The maximum height of any square is 2.

After the second drop of `positions[1] = [2, 3]: __aaa __aaa __aaa _aa__ _aa__ --------------` The maximum height of any square is 5. The larger square stays on top of the smaller square despite where its center of gravity is, because squares are infinitely sticky on their bottom edge.

After the third drop of `positions[1] = [6, 1]: __aaa __aaa __aaa _aa _aa___a --------------` The maximum height of any square is still 5. Thus, we return an answer of `[2, 5, 5]`.

Example 2:

``````Input: [[100, 100], [200, 100]]
Output: [100, 100]
Explanation: Adjacent squares don't get stuck prematurely - only their bottom edge can stick to surfaces.
``````

Note:

• `1 <= positions.length <= 1000`.
• `1 <= positions[i][0] <= 10^8`.
• `1 <= positions[i][1] <= 10^6`.

## 题目大意 #

``````输入: [[1, 2], [2, 3], [6, 1]]

_aa
_aa
-------

__aaa
__aaa
__aaa
_aa__
_aa__
--------------

__aaa
__aaa
__aaa
_aa
_aa___a
--------------

``````

• 1 <= positions.length <= 1000.
• 1 <= positions[i][0] <= 10^8.
• 1 <= positions[i][1] <= 10^6.

## 解题思路 #

• 给出一个二维数组，每个一维数组中只有 2 个值，分别代表的是正方形砖块所在 x 轴的坐标起始点，和边长。要求输出每次砖块落下以后，当前最大的高度。正方形砖块落下如同俄罗斯方块，落下的过程中如果遇到了砖块会落在砖块的上面。如果砖块摞起来了以后，下方有空间，是不可能再把砖块挪进去的，因为此题砖块只会垂直落下，不会水平移动(这一点和俄罗斯方块不同)。
• 这一题可以用线段树解答。由于方块在 x 轴上的坐标范围特别大，如果不离散化，这一题就会 MTE。所以首先去重 - 排序 - 离散化。先把每个砖块所在区间都算出来，每个正方形的方块所在区间是 `[pos[0] , pos[0]+pos[1]-1]` ，为什么右边界要减一呢？因为每个方块占据的区间其实应该是左闭右开的，即 `[pos[0] , pos[0]+pos[1])`，如果右边是开的，那么这个边界会被 2 个区间查询共用，从而导致错误结果。例如 [2,3]，[3,4]，这两个区间的砖块实际是不会摞在一起的。但是如果右边都是闭区间，用线段树 query 查询的时候，会都找到 [3，3]，从而导致这两个区间都会判断 3 这一点的情况。正确的做法应该是 [2,3)，[3,4）这样就避免了上述可能导致错误的情况了。离散化以后，所有的坐标区间都在 0~n 之间了。
• 遍历每个砖块所在区间，先查询这个区间内的值，再加上当前砖块的高度，即为这个区间的最新高度。并更新该区间的值。更新区间的值用到懒惰更新。然后和动态维护的当前最大高度进行比较，将最大值放入最终输出的数组中。
• 类似的题目有：第 715 题，第 218 题，第 732 题。第 715 题是区间更新定值(不是增减)，第 218 题可以用扫描线，第 732 题和本题类似，也是俄罗斯方块的题目，但是第 732 题的俄罗斯方块的方块会“断裂”。
• leetcode 上也有线段树的讲解： Get Solutions to Interview Questions

## 代码 #

``````
package leetcode

import (
"sort"

"github.com/halfrost/LeetCode-Go/template"
)

func fallingSquares(positions [][]int) []int {
st, ans, posMap, maxHeight := template.SegmentTree{}, make([]int, 0, len(positions)), discretization(positions), 0
tmp := make([]int, len(posMap))
st.Init(tmp, func(i, j int) int {
return max(i, j)
})
for _, p := range positions {
h := st.QueryLazy(posMap[p[0]], posMap[p[0]+p[1]-1]) + p[1]
st.UpdateLazy(posMap[p[0]], posMap[p[0]+p[1]-1], h)
maxHeight = max(maxHeight, h)
ans = append(ans, maxHeight)
}
return ans
}

func discretization(positions [][]int) map[int]int {
tmpMap, posArray, posMap := map[int]int{}, []int{}, map[int]int{}
for _, pos := range positions {
tmpMap[pos[0]]++
tmpMap[pos[0]+pos[1]-1]++
}
for k := range tmpMap {
posArray = append(posArray, k)
}
sort.Ints(posArray)
for i, pos := range posArray {
posMap[pos] = i
}
return posMap
}

``````

Sep 6, 2020