O(n)复杂度中子段中最大值的最小值

Question

我几天前采访了亚马逊.我无法回答其中一个让我满意的问题.我在采访后试图得到答案,但到目前为止我还没有成功.这是一个问题:

你有一个大小为n的整数数组.给你参数k在哪里k < n.对于k阵列中每个连续元素大小的每个段,您需要计算最大值.您只需返回这些最大值的最小值.

例如给出1 2 3 1 1 2 1 1 1,k = 3答案是1.
该段将是1 2 3,2 3 1,3 1 1,1 1 2,1 2 1,2 1 1,1 1 1.
每个段中的最大的值是3,3,3,2,2,2,1.因此,答案是
这些值中的最小值.11

我想出的最佳答案是复杂度O(n log k).我所做的是创建一个带有第一个k元素的二叉搜索树,获取树中的最大值并将其保存在变量中minOfMax,然后一次循环一个元素与数组中的其余元素,删除前一个元素从二叉搜索树段,插入新段的最后一个元素树,树中得到最大的元素,并将其与比较minOfMax中留下minOfMax了两个最小值.

理想的答案需要具有复杂度O(n).谢谢.

Answer 1

有一种非常聪明的方法可以解决这个问题.我们的想法是,可以构建一个队列数据结构,该结构在分摊的O(1)时间内支持enqueue,dequeue和find-max(有很多方法可以做到这一点;在原始问题中有两种解释).获得此数据结构后,首先在O(k)时间将数组中的前k个元素添加到队列中.由于队列支持O(1)find-max,因此您可以在O(1)时间内找到这些k元素的最大值.然后,连续从队列中出队一个元素,并将下一个数组元素排入队列(在O(1)时间内).然后,您可以在O(1)中查询每个k元素子阵列的最大值.如果您跟踪在数组过程中看到的这些值的最小值,那么您有一个O(n)时间,O(k)空间算法,用于查找k元素子阵列的最小最大值.

希望这可以帮助!

Answer 2

@ templatetypedef的答案有效,但我认为我有更直接的方法.

首先计算以下(闭合)间隔的最大值:

[k-1, k-1]
[k-2, k-1]
[k-3, k-1]
...
[0, k-1]

注意,这些中的每一个都可以在前一个的恒定时间内计算.

接下来,计算这些间隔的最大值:

[k, k]
[k, k+1]
[k, k+2]
...
[k, 2k-1]

现在这些间隔:

[2k-1, 2k-1]
[2k-2, 2k-1]
[2k-3, 2k-1]
...
[k+1, 2k-1]

接下来,您将执行从2k到3k-1("前进间隔"),然后从3k-1到2k + 1("向后间隔")的间隔.依此类推,直到你到达阵列的末尾.

将所有这些放在一张大桌子上.请注意,此表中的每个条目都需要恒定的时间来计算.观察表中最多有2*n个间隔(因为每个元素在"前向间隔"的右侧出现一次,而在"向后间隔"的左侧出现一次).

现在,如果[a,b]是宽度为k的任何间隔,它必须恰好包含0,k,2k中的一个,......

假设它包含m*k.

观察到区间[a,m*k-1]和[m*k,b]都在我们表格的某处.因此,我们可以简单地查找每个的最大值,这两个值的最大值是区间[a,b]的最大值.

因此,对于宽度为k的任何间隔,我们可以使用我们的表在恒定时间内获得最大值.我们可以在O(n)时间生成表.结果如下.