-3

给定一个数字数组和一个滑动窗口大小，如何获得所有滑动窗口中的最大数字？

例如输入数组为{2, 3, 4, 2, 6, 2, 5, 1}，滑动窗口大小为3，则输出最大值为{4, 4, 6, 6, 6, 5}。滑动窗口的大小是传递给您的变量。

滑动窗口基本上是从特定索引开始的原始数组的子数组。例如，在索引 0 处，大小为 3，它是前 3 个元素。在索引 1 处，大小为 3，它是第 2、第 3 和第 4 个元素。

你将如何用 Java 或任何其他编程语言解决这个问题？或者伪代码，如果你愿意的话。

（注意：这不是一个家庭作业问题，只是我在一个网站上发现的一个问题，我有自己的解决方案，但想与其他人进行比较，之后我也会在下面发布我的解决方案）

4

3 回答 3

1

您可以在 中执行此操作O(N*Log(W))，其中N是数组W的大小，并且是滑动窗口的大小。

使用二叉树存储第一个W数字。对于以下N-W步骤，max从树中获取输出值，将当前位置的元素添加i到树中，然后从树中删除 at 的元素i-W。这些操作都是O(Log(W))，对于总体时序O(N*Log(W))：

int[] data = new int[] {2, 3, 4, 2, 6, 2, 5, 1};
int W = 3;
TreeMap<Integer,Integer> counts = new TreeMap<Integer,Integer>();
for (int i = 0 ; i != W ; i++) {
    if (counts.containsKey(data[i])) {
        counts.put(data[i], counts.get(data[i])+1);
    } else {
        counts.put(data[i], 1);
    }
}
for (int i = W ; i != data.length ; i++) {
    Integer max = counts.lastKey();
    System.out.println(max);
    int tmp = counts.get(data[i-W])-1;
    if (tmp != 0) {
        counts.put(data[i-W], tmp);
    } else {
        counts.remove(data[i-W]);
    }
    if (counts.containsKey(data[i])) {
        counts.put(data[i], counts.get(data[i])+1);
    } else {
        counts.put(data[i], 1);
    }
}
System.out.println(counts.lastKey());

ideone 上的演示。

于 2013-07-17T19:54:40.583 回答
1

既然你不介意伪代码/其他语言，那么这个（在 Python 中）怎么样：

l = [2, 3, 4, 2, 6, 2, 5, 1]
result = [max(l[i:i+3]) for i in range(len(l)-2)]
于 2013-07-17T19:58:30.993 回答
0

如果我试图解决这样的问题，我总是从天真的算法开始。逐个窗口扫描数组有什么问题？好吧，当你看到它的不足之处（你一遍又一遍地重复相同的比较）时，你可以开始寻找其他方法。

通过将初始阵列可视化为山脉来建议一种方法：找到最高峰。没有什么比这更高了，所以这是它周围窗户的最大值。现在您可以递归地进行。可能还有其他更好的方法。

于 2013-07-17T19:59:22.420 回答