website/content.en/ChapterFour/0600~0699/0699.Falling-Squares.md
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.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:
[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.
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
}