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.

题目大意 #

在无限长的数轴(即 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]

注意:

  • 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
}


⬅️上一页

下一页➡️

Calendar Apr 8, 2023
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者