子段中最大值的最小值 ... O(n) 复杂度 [英] Minimum value of maximum values in sub-segments ... in O(n) complexity
问题描述
我几天前采访了亚马逊.我无法回答他们向我提出的问题之一.我试图在面试后得到答案，但到目前为止我还没有成功.问题来了:
你有一个大小为 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 中，然后在 a 处循环一个元素与数组中剩余元素的时间，从二叉搜索树中删除前一段的第一个元素，将新段的最后一个元素插入树中，获取树中的最大元素并与minOfMax进行比较 在 minOfMax 中保留两者的最小值.
理想的答案需要复杂度为 O(n).谢谢你.
有一个非常聪明的方法可以做到这一点，与 这个早先的问题.这个想法是可以构建一个队列数据结构，在分摊 O(1) 时间内支持入队、出队和 find-max(有很多方法可以做到这一点；原始问题中解释了两种).获得此数据结构后，首先在 O(k) 时间内将数组中的前 k 个元素添加到队列中.由于队列支持 O(1) find-max，您可以在 O(1) 时间内找到这 k 个元素的最大值.然后，不断地从队列中取出一个元素并将下一个数组元素入队(在 O(1) 时间内).然后，您可以在 O(1) 中查询这些 k 元素子数组中的每一个的最大值是多少.如果您跟踪在数组过程中看到的这些值的最小值，那么您就有了一个 O(n) 时间、O(k) 空间的算法来找到 k 元素子数组的最小最大值.
希望这有帮助！
I interviewed with Amazon a few days ago. I could not answer one of the questions the asked me to their satisfaction. I have tried to get the answer after the interview but I have not been successful so far. Here is the question:
You have an array of integers of size n. You are given parameter k where k < n. For each segment of consecutive elements of size k in the array you need to calculate the maximum value. You only need to return the minimum value of these maximum values.
For instance given 1 2 3 1 1 2 1 1 1 and k = 3 the answer is 1.
The segments would be 1 2 3, 2 3 1, 3 1 1, 1 1 2, 1 2 1, 2 1 1, 1 1 1.
The maximum values in each segment are 3, 3, 3, 2, 2, 2, 1.
The minimum of these values are 1 thus the answer is 1.
The best answer I came up with is of complexity O(n log k). What I do is to create a binary search tree with the first k elements, get the maximum value in the tree and save it in variable minOfMax, then loop one element at a time with the remaining elements in the array, remove the first element in the previous segment from the binary search tree, insert the last element of the new segment in the tree, get the maximum element in the tree and compare it with minOfMax leaving in minOfMax the min value of the two.
The ideal answer needs to be of complexity O(n). Thank you.
There is a very clever way to do this that's related to this earlier question. The idea is that it's possible to build a queue data structure that supports enqueue, dequeue, and find-max in amortized O(1) time (there are many ways to do this; two are explained in the original question). Once you have this data structure, begin by adding the first k elements from the array into the queue in O(k) time. Since the queue supports O(1) find-max, you can find the maximum of these k elements in O(1) time. Then, continuously dequeue an element from the queue and enqueue (in O(1) time) the next array element. You can then query in O(1) what the maximum of each of these k-element subarrays are. If you track the minimum of these values that you see over the course of the array, then you have an O(n)-time, O(k)-space algorithm for finding the minimum maximum of the k-element subarrays.
Hope this helps!
这篇关于子段中最大值的最小值 ... O(n) 复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
