699. Falling Squares #
Problem #
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.
Main Idea of the Problem #
On an infinitely long number line（i.e. the x-axis）, we place the corresponding square blocks according to the given order. The i-th falling block（positions[i] = (left, side_length)）is a square, where left indicates the position of the leftmost point of the block(positions[i][0]), side_length indicates the side length of the block(positions[i][1]).
The bottom edge of each block is parallel to the number line（i.e. the x-axis）, and it falls from a height higher than all currently landed blocks. Only after the previous block has finished falling and remains still does the new block start to fall. The bottom edge of the blocks has very strong stickiness, and will remain fixed to any length of surface they contact（whether the number line or other blocks）. Adjacent falling edges will not stick together prematurely, because only the bottom edge is sticky.
Return a stack height list ans . Each stack height ans[i] indicates the highest height of the stack of all currently settled blocks after the falling of the blocks represented by positions[0], positions[1], …, positions[i] has ended.
Example 1:
Input: [[1, 2], [2, 3], [6, 1]]
Output: [2, 5, 5]
Explanation:
The first block positions[0] = [1, 2] falls:
_aa
_aa
-------
The maximum height of the block is 2 .
The second block positions[1] = [2, 3] falls:
__aaa
__aaa
__aaa
_aa__
_aa__
--------------
The maximum height of the block is5.
The large block stays on top of the smaller block, no matter where its center of gravity is, because the bottom edge of the block has very strong stickiness.
The third block positions[1] = [6, 1] falls:
__aaa
__aaa
__aaa
_aa
_aa___a
--------------
The maximum height of the block is5.
Therefore, we return the result[2, 5, 5].
Note:
- 1 <= positions.length <= 1000.
- 1 <= positions[i][0] <= 10^8.
- 1 <= positions[i][1] <= 10^6.
Solution Approach #
- Given a two-dimensional array, each one-dimensional array contains only 2 values, representing respectively the starting coordinate on the x-axis where the square brick is located, and the side length. The requirement is to output the current maximum height after each brick falls. The square bricks fall like Tetris blocks; if a brick encounters another brick while falling, it will land on top of that brick. After bricks are stacked, if there is space below, it is impossible to move the brick into it, because in this problem bricks only fall vertically and do not move horizontally(this point is different from Tetris).
- This problem can be solved with a segment tree. Since the coordinate range of the blocks on the x-axis is especially large, without discretization, this problem would MTE. So first deduplicate - sort - discretize. First calculate the interval where each brick is located; the interval for each square block is
[pos[0] , pos[0]+pos[1]-1]，why does the right boundary need to subtract one? Because the interval occupied by each block should actually be left-closed and right-open, i.e.[pos[0] , pos[0]+pos[1]); if the right side is open, then this boundary will be shared by 2 interval queries, thus leading to an incorrect result. For example [2,3]，[3,4], the bricks in these two intervals will not actually be stacked together. But if the right sides are all closed intervals, when querying with segment tree query, both will find [3，3], thus causing both intervals to consider the situation at the point 3. The correct approach should be [2,3)，[3,4）which avoids the above situation that could lead to errors. After discretization, all coordinate intervals are between 0~n. - Traverse the interval where each brick is located, first query the value within this interval, then add the height of the current brick, which is the latest height of this interval. And update the value of this interval. Updating the value of the interval uses lazy updates. Then compare it with the dynamically maintained current maximum height, and put the maximum value into the final output array.
- Similar problems include: Problem 715, Problem 218, Problem 732. Problem 715 is interval update to a fixed value(not increase or decrease), Problem 218 can use a sweep line, Problem 732 is similar to this problem and is also a Tetris problem, but the Tetris blocks in Problem 732 will “break”.
- There is also an explanation of segment trees on leetcode: Get Solutions to Interview Questions
Code #
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
}
中文