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

Question

面试题:- 给定一个数组和一个整数 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)。

Answer 1

只需遍历数组并在 self-balancing 中保留 k 个最后元素binary tree .
向此类树添加元素、删除元素并查找当前最大成本 O(logk)。

大多数语言都为此类树提供标准实现。在 STL、IIRC 中，它是 MultiSet。在 Java 中，您将使用 TreeMap( map ，因为您需要保持计数，每个元素出现了多少次，而 Java 不提供多集合)。

伪代码

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());
    }
}