[Swift]LeetCode699. 掉落的方块 | Falling Squares
On an infinite number line (x-axis),we drop given squares in the order they are given. The? 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? Example 1: Input: [[1,2],[2,3],[6,1]] Output: [2,5,5] Explanation: After the first drop of After the second drop of After the third drop of 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:
在无限长的数轴(即 x 轴)上,我们根据给定的顺序放置对应的正方形方块。 第? 每个方块的底部边缘平行于数轴(即 x 轴),并且从一个比目前所有的落地方块更高的高度掉落而下。在上一个方块结束掉落,并保持静止后,才开始掉落新方块。 方块的底边具有非常大的粘性,并将保持固定在它们所接触的任何长度表面上(无论是数轴还是其他方块)。邻接掉落的边不会过早地粘合在一起, 返回一个堆叠高度列表? 示例 1: 输入: [[1,1]] 输出: [2,5] 解释: 第一个方块 掉落: 方块最大高度为 2 。 第二个方块 掉落: 方块最大高度为5。 大的方块保持在较小的方块的顶部,不论它的重心在哪里,因为方块的底部边缘有非常大的粘性。 第三个方块 掉落: 方块最大高度为5。 因此,我们返回结果?positions[0] = [1,2]_aa _aa -------positions[1] = [2,3]__aaa __aaa __aaa _aa__ _aa__ --------------positions[1] = [6,1]__aaa __aaa __aaa _aa _aa___a --------------[2,5]。 示例 2: 输入: [[100,100]] 输出: [100,100] 解释: 相邻的方块不会过早地卡住,只有它们的底部边缘才能粘在表面上。? 注意:
Runtime:?1272 ms
Memory Usage:?19.5 MB
1 class Solution { 2 func fallingSquares(_ positions: [[Int]]) -> [Int] { 3 var n:Int = positions.count 4 var cur:Int = 0 5 var heights:[Int] = [Int](repeating:0,count:n) 6 var res:[Int] = [Int]() 7 for i in 0..<n 8 { 9 var len:Int = positions[i].last! 10 var left:Int = positions[i].first! 11 var right:Int = left + len 12 heights[i] += len 13 for j in (i + 1)..<n 14 { 15 var l:Int = positions[j].first! 16 var r:Int = l + positions[j].last! 17 if l < right && r > left 18 { 19 heights[j] = max(heights[j],heights[i]) 20 } 21 } 22 } 23 for h in heights 24 { 25 cur = max(cur,h); 26 res.append(cur) 27 } 28 return res 29 } 30 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |