algorithm - 切片堆叠框的线性时间算法

Question

我有一个时间限制相当有限的问题，想看看我是否能得到正确方向的插入。

问题是:

You are presented with a wall with columns of different heights. Each column heights is represented as a non-zero integers.

Input state is defined using an array H of length N, containing heights of each of the N columns on the screen, for example:

Slicing the snapshot at a given height leaves a number of solid pieces above that height. E.g. slicing at level 2 would cut 3 solid pieces:

Slicing at level 1 would also cut 3 solid pieces:

Similarly, slicing at level 0 would return a single (one) solid piece, while slicing at level 3 wouldn't cut any pieces.

Requirement: Given an array of slice heights S of length M, containing all levels at which a "slice" should be performed, return an array of length M containing numbers of cut pieces for each respective cut.

For example, given the input H = {2, 1, 3, 2, 3, 1, 1, 2} and S = { 0, 1, 2, 3 }, the program should return quantities {1, 3, 3, 0}, according to the examples above.

Both N and M are in the range of around 20,000, but heights in each array can reach up to 1,000,000.

Both time and space worst-case complexity for the solution cannot exceed O(N + M + max(M) + max(N)).

最后一个约束令我感到困惑:它基本上意味着我不能有任何嵌套的 for 循环，而且我似乎无法逃避这一点。

显然，需要进行一些巧妙的预处理才能在每个切片的 O(1) 中产生最终结果，但我还没有想出它。

我继续为每个切片级别创建一个切割数数组，然后在遍历 H 时更新所有这些数组，但结果是 O(N* M)，因为我需要更新所有较低的高度级别。

是否有适合这项任务的数据结构？

Answer 1

对于一个高度处的每个棋子，必须有两条边与该高度相交，并且根据“棋子”的定义，这些边的集合中的成员都必须是不同的。所以 block 数是集合中边数的一半。

此外，与特定高度相交的边数是从低于或在该高度开始的边数减去在低于或在该高度处结束的边数。

因此，我们可以这样计算件数:

• 创建数组Accumulator尺寸max(S)用零填充。
• 遍历 H ，并为您遇到的每个垂直边缘添加一个 +1在索引 i在Accumulator对应边缘下端的高度，并添加一个-1在索引 j在对应于边缘的上端。我们将“地面”计为零。确保包括前缘和后缘!
• 遍历 Accumulator并在每个单元格中插入直到并包括它的所有单元格的总和(O(max(S)) 时间，如果你保持运行总和)
• 将 Accumulator 中的每个值相除乘以 2 得到每个高度的棋子数。
• 读出S中高度对应的棋子数.

例子:

边的端点从左到右分别是

0,2
1,2
1,3
2,3
2,3
1,3
1,3
0,3

所以我们的 Accumulator数组看起来像这样:

{2, 4, 0, -6}

在累积步骤之后，看起来像这样:

{2, 6, 6, 0}

这意味着零件数是

{1, 3, 3, 0} 

作为警告，我只是当场想出这个，所以虽然它感觉正确，但我无法证明它是否真的正确。令人鼓舞的是，它也适用于我尝试过的其他一些 token 示例。