用于切片堆积箱的线性时间算法

Question

我有一个问题,它有一个相当有限的时间限制,并想看看我是否可以在正确的方向上轻推.

这是问题所在:

你会看到一面墙,上面有不同高度的柱子.每列高度表示为非零整数.

输入状态使用H长度数组定义N,包含N屏幕上每列的高度,例如:

M包含每个相应切割的切割件数量的长度数组.

例如,根据上面的示例,给定输入H = {2, 1, 3, 2, 3, 1, 1, 2}并且S = { 0, 1, 2, 3 }程序应返回数量{1, 3, 3, 0}.

都N和M在左右的范围内20,000,但在每个阵列中的高度可达到1,000,000.

解决方案的时间和空间最坏情况复杂性都不能超过 O(N + M + max(M) + max(N)).

最后一个约束是让我感到困惑的:它基本上意味着我不能拥有任何嵌套的for-loops,而我似乎无法逃脱这一点.

显然,有一些聪明的预处理需要在O(1)每个切片中产生最终结果,但我无法想出它.

我继续为每个切片级别创建一个切割数字数组,然后在迭代时更新所有切割数字H,但事实证明O(N*M),因为我需要更新所有较低的高度级别.

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

Answer 1

对于高度上的每个部件,必须有两个与该高度相交的边缘,并且通过"部件"的定义,这组边缘的成员必须全部是不同的.因此,件数是集合中边缘数量的一半.

此外,与特定高度相交的边缘的数量是在低于或在该高度处开始的边缘的数量减去在其下方或在其处完成的边缘的数量.

因此,我们可以通过这种方式计算出件数:

• 创建一个用零填充Accumulator的大小数组max(S).
• 迭代H,并且对于您遇到的每个垂直边缘+1,i在Accumulator对应于边缘下端高度-1的索引j处添加a,并在对应于边缘上端的索引处添加a .我们将"地面"计为零.确保包括前缘和后缘!
• 迭代Accumulator并在每个单元格中插入所有单元格的总和,包括它(O(max(S))如果保持运行总和,则为时间)
• 将每个值除以Accumulator2得到每个高度的碎片数.
• 读出与高度相对应的件数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} 

作为一个警告,我刚刚在现场提出这个问题,所以虽然感觉正确,但我没有证据确实是这样.令人鼓舞的是,它也尝试了我尝试过的其他几个例子.