我几天前采访了亚马逊.我无法回答其中一个让我满意的问题.我在采访后试图得到答案,但到目前为止我还没有成功.这是一个问题:
你有一个大小为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 …
我有一个类似的阵列
[5.5, 6.0, 6.0, 6.5, 6.0, 5.5, 5.5, 5.0, 4.5].
该数组的所有数字相差0.5,两个连续数字的最大差值也为0.5(它们可以相同;如示例中所示).并且有一个移动间隔或框,其中包含例如3个连续数字,如下所示:
[(5.5, 6.0, 6.0), 6.5, 6.0, 5.5, 5.5, 5.0, 4.5] # min: 5.5, max: 6.0
并且盒子一个接一个地向右移动:
[5.5, (6.0, 6.0, 6.5), 6.0, 5.5, 5.5, 5.0, 4.5] # min: 6.0, max: 6.5
[5.5, 6.0, (6.0, 6.5, 6.0), 5.5, 5.5, 5.0, 4.5] # min: 6.0, max: 6.5
问题是,如何在每个时间框移动时找到框内数字的最小值和最大值？
当盒子和数组的大小像这个例子那样小时,我可以处理它,但我需要将它应用于数组大小100000和盒子大小10000.使用我的方法(我每次使用for循环计算每个max和min盒子通过),花了太多时间(我有100多个阵列要做,需要反复运行).有一些时间限制,所以我需要在0.5秒内像一次计算一样运行它.