0699. Falling Squares

题目信息

题号:

0699

难度:

Hard

主题:

下落正方形、半开水平区间、重叠堆叠、前缀最高高度

原题:

LeetCode 0699

重点:

每个正方形按输入顺序落下、水平投影正长度重叠时才能堆叠、仅边界接触不算重叠、每次返回当前全局最高高度

题目重述

给定数组 positions,其中 positions[i] = [left_i, sideLength_i] 表示第 i 个边长为 sideLength_i 的正方形,其水平投影是半开区间 [left_i, left_i + sideLength_i)。正方形按输入顺序从上方向下垂直落下。

一个正方形会落在地面上,或落在此前已停止且与它的水平投影具有正长度重叠的正方形最高顶部;仅在端点接触的投影不算重叠。正方形停止后不再移动。返回数组 answer,其中 answer[i] 是前 i+1 个正方形落下后所有堆叠结构的最高高度。positions.length 位于 [1, 1000],left_i 位于 [1, 10^8],边长位于 [1, 10^6]。

自建示例

边界接触不产生堆叠:

输入:positions = [[1,2],[3,2],[2,2]]
输出:[2,2,4]
解释:前两个投影 [1,3) 与 [3,5) 仅在端点接触,因此都落在地面;第三个投影 [2,4) 与前两者均有正长度重叠,落在高度 2 上,顶部达到 4。

只有一个正方形:

输入:positions = [[5,3]]
输出:[3]
解释:正方形直接落在地面,落下后的全局最高高度等于其边长 3。