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

Question

几天前我面试了亚马逊。我无法对他们提出的问题做出令他们满意的回答。我曾试图在面试后得到答案，但到目前为止还没有成功。问题是：

你有一个大小为 n 的整数数组。您将获得参数k，其中k 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)。 谢谢。

Answer 1

有一种非常聪明的方法可以做到这一点，与 这个较早的问题。这个想法是可以构建一个支持在摊销 O(1) 时间内入队、出队和 find-max 的队列数据结构< /a> （有很多方法可以做到这一点；原始问题中解释了两种方法）。一旦有了这个数据结构，就开始在 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) 时间内生成表。结果如下。

Answer 3

我在 C# 中实现（并评论）了 templatetypedef 的答案。

n 是数组长度，k 是窗口大小。

    public static void printKMax(int[] arr, int n, int k)
    {
        Deque<int> qi = new Deque<int>(); 
        int i;

        for (i=0 ; i < k ; i++) // The first window of the array
        {
            while ((qi.Count > 0) && (arr[i] >= arr[qi.PeekBack()]))
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }

        for(i=k ; i < n ; ++i)
        {
            Console.WriteLine(arr[qi.PeekFront()]); // the first item is the largest element in previous window. The second item is its index.

            while (qi.Count > 0 && qi.PeekFront() <= i - k) 
            {
                qi.PopFront(); //When it's out of its window k 
            }
            while (qi.Count>0 && arr[i] >= arr[qi.PeekBack()]) 
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }
        Console.WriteLine(arr[qi.PeekFront()]);
    }