最大值的细分市场最小值......在O（n）的复杂性 [英] Minimum value of maximum values in sub-segments ... in O(n) complexity

问题描述

我与亚马逊前几天接受采访。我不能回答的让我自己满意的问题之一。我曾试图让面试后的答案，但我一直没成功为止。这里有一个问题：

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:

您有一个大小为整数数组。您将得到参数 K ，其中 K＆LT; ñ。为阵列中的大小 K 的连续元素的每一段需要计算的最大值。你只需要返回这些最大值的最小值。

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.

例如给出 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 ， 111 。
每个段的最大值是 3 ， 3 ， 3 ， 2 ， 2 ， 2 ， 1 。
这些值的最小值为 1 因此，答案是 1 。

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.

我想出了IS的复杂度为O最好的答案（N日志K）。我要做的是创建的第一个二叉搜索树氏/ code>元素，拿在树中的最大值，并将其保存在变量 minOfMax ，在与阵列中的其余元件的时间，然后循环一种元素，从所述二分搜索树中删除在previous段的第一元件，插入到树中的新段的最后一个元素，得到最大的元素在树中，并用 minOfMax 比较留下 minOfMax 两者的最小值。

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.

理想的答案必须是复杂度为O（N）。 谢谢。

The ideal answer needs to be of complexity O(n). Thank you.

推荐答案

有一个很聪明的方式来做到这一点的有关为 <一个href="http://stackoverflow.com/questions/7065926/how-to-find-maximum-of-each-subarray-of-some-fixed-given-length-in-a-given-array/7069038#7069038">this前面的问题 。我们的想法是，它是不可能建立一个支持入队，出队队列中的数据结构，并找到-Max在摊销O（1）时间（有很多方法可以做到这一点;二是在原来的问题进行了说明）。一旦你有了这个数据结构，通过增加从数组的第k个元素到队列中的O（k）的时间开始。由于队列支持O（1）发现-MAX，你可以找到这些k个元素的O（1）时间的最大值。然后，连续出列从队列和排队的元件（在O（1）时间）的下一个数组元素。然后，您可以在O查询（1）什么这些K-元子阵中最大的。如果你跟踪最小，你看到过阵的过程中这些值，那么你必须为O（n） - 时间，O（K）-space算法寻找最小最大的K-元件子阵的。

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.

希望这有助于！

这篇关于最大值的细分市场最小值......在O（n）的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！