前几天去亚马逊面试了。我无法回答他们问我的问题之一。我试图在面试后得到答案，但到目前为止我还没有成功。下面是问题:
你有一个大小为 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 .
这些值中的最小值是 1因此答案是1 .
我想出的最佳答案是复杂度 O(n log k)。我所做的是用第一个 k 创建一个二叉搜索树元素，获取树中的最大值，保存在变量minOfMax中，然后用数组中的剩余元素一次循环一个元素，从二叉搜索树中删除前一段中的第一个元素，将新段的最后一个元素插入树中，得到树中的最大元素并且将其与 minOfMax 进行比较离开minOfMax两者的最小值。
理想的答案需要复杂度为 O(n)。 谢谢。
最佳答案
有一个非常聪明的方法可以做到这一点，它与 this earlier question 有关。 。这个想法是可以构建一个 queue data structure that supports enqueue, dequeue, and find-max in amortized O(1) time (有很多方法可以做到这一点；原始问题中解释了两种)。拥有此数据结构后，首先在 O(k) 时间内将数组中的前 k 个元素添加到队列中。由于队列支持 O(1) find-max，因此可以在 O(1) 时间内找到这 k 个元素中的最大值。然后，不断地从队列中取出一个元素并将下一个数组元素放入队列(在 O(1) 时间内)。然后，您可以在 O(1) 中查询这些 k 元素子数组中每一个的最大值是多少。如果您跟踪在数组过程中看到的这些值的最小值，那么您就有了一个 O(n) 时间、O(k) 空间算法来查找 k 元素子数组的最小最大值。
希望这对您有所帮助!
关于arrays - 子段中最大值的最小值......在 O(n) 复杂度中，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8499227/