找出长度为k的每个子数组中最大的数

Question

找出长度为k的每个子数组中最大的数

3

面试题：给定一个数组和一个整数k，找出每个大小为k的连续子数组的最大值。

Sample Input :

1 2 3 1 4 5 2 3 6 

3 [ value of k ]


Sample Output :
3
3
4
5
5
5
6

我想不出比暴力更好的方法了。最坏情况是当数组按降序排序时，时间复杂度为O(nk)。

- perseus

3个回答

2

您可以用O(n)的时间和O(n)的空间完成此操作。

将数组分成每个块。

[a1 a2 ... ak] [a(k+1) ... a2k] ...

对于每个块，维护两个块，左块和右块。

左块的第i个元素将是从左边选择的i个元素中的最大值。右块的第i个元素将是从右边选择的i个元素中的最大值。

对于每个块k，您将有两个这样的块。

现在，如果要在范围a[i... i+k]中查找最大值，则表示元素跨越k个以上块。

[j-k+1 ... i i+1 ... j] [j+1 ... i+k ... j+k]

您只需要找到第一个块中从i到j的RightMax和第二个块中从j+1到i+k的left max的最大值即可。

- Aryabhatta

不错的想法。值得注意的是，“块”不一定要物理上分开，它可以只是长度为n的2个数组。至于堆的适用性，我已经在我的答案中进行了评论。 - Nikita Rybak

2

@Nikita：如果您喜欢这个问题，我建议您看一下区间最小查询问题。在O(n)时间内，您可以执行预处理步骤，以便回答任何形式的查询Min(a[i],…,a[j])（而不仅仅是j-i=k）可以在O(1)时间内完成。我同意您对堆的评估。 - Aryabhatta

我认为这个解决方案并不比第一个答案更好，因为你需要对每个块进行排序以保持其属性。因此，总时间复杂度将是O(n/k * k * logk) = O(nlogk)，这与第一个答案相同，我是正确的吗？... - superb

@superb：不需要排序，当你遍历数组时，可以创建两个块中的一个。要创建另一个块，可以反向遍历。 - Aryabhatta

1

希望这是你正在寻找的解决方案：

def MaxContigousSum(lst, n):
m = [0]
if lst[0] > 0:
    m[0] = lst[0]
maxsum = m[0]
for i in range(1, n):
    if m[i - 1] + lst[i] > 0:
        m.append(m[i - 1] + lst[i])
    else:
        m.append(0)
    if m[i] > maxsum:
        maxsum = m[i]
return maxsum

lst = [-2, 11, -4, 13, -5, 2, 1, -3, 4, -2, -1, -6, -9]
print MaxContigousSum(lst, len(lst))
**Output**
20 for [11, -4, 13]

- Love Sharma

我建议您再次仔细阅读原帖的问题。该问题并不是要求“最大连续和”，而是要在每个子数组中寻找“最大元素”。 - narengi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nikita Rybak · Accepted Answer

只需遍历数组，同时在自平衡二叉树中保留最后的k个元素。
在这样的树中添加、删除元素和查找当前最大值的成本为 O(logk)。

大多数编程语言都提供了标准的实现方法。在STL中，我记得是MultiSet。在Java中，您可以使用TreeMap（map，因为需要计算每个元素出现的次数，而Java不提供 Multi- 集合）。

伪代码

for (int i = 0; i < n; ++i) {
    tree.add(a[i]);

    if (tree.size() > k) {
        tree.remove(a[i - k]);
    }

    if (tree.size() == k) {
        print(tree.max());
    }
}