golang力扣leetcode 699.掉落的方块_力扣掉落的方块

699.掉落的方块

699.掉落的方块

题解

题目：相当于俄罗斯方块下落，如果当前方块下面有方块，就会叠上去，给一个方块数组，求每个方块的高度，不过这句话要做修改，是记录目前所有已经落稳的== 方块堆叠的最高高度 ==，即如果当前方块的高度小于之前堆叠的最高高度，当前高度赋值为堆叠的最高高度

思路：很明显的区间查询和区间修改，用线段树来做，可惜我不会，直接用暴力方法

1.遍历方块数组
2.遍历当前方块之前的方块数组
3.如果当前方块与之前的方块重合
	则height[i] = max(height[i], height[j]+curHeight)
1
2
3
4

代码

func fallingSquares(positions [][]int) []int {
	height := make([]int, len(positions))
	for i, v := range positions { //当前这个方块
		l1, r1, curHeight := v[0], v[0]+v[1]-1, v[1]
		height[i] = curHeight
		for j, vv := range positions[:i] { //该点之前落下的方块
			l2, r2 := vv[0], vv[0]+vv[1]-1
			if !(r1 < l2 || l1 > r2) { //如果两个方块有重叠
				height[i] = max(height[i], height[j]+curHeight)
			}
		}
	}
	for i := 1; i < len(height); i++ {
		height[i] = max(height[i], height[i-1])
	}
	return height
}
func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23