在数组中发现的最大尺寸为k的每个窗口 [英] Finding maximum for every window of size k in an array

问题描述

由于大小n和k的数组，你是怎么找到的最大尺寸为k的每一个连续的子阵？

Given an array of size n and k, how do you find the maximum for every contiguous subarray of size k?

例如

arr = 1 5 2 6 3 1 24 7
k = 3
ans = 5 6 6 6 24 24

我想具有大小为k的阵列，并且每个步骤驱逐的最后一个元件出并添加新元素，并找到最大之间这一点。这导致了O（NK）运行时间。有没有更好的方式来做到这一点？

I was thinking of having an array of size k and each step evict the last element out and add the new element and find maximum among that. It leads to a running time of O(nk). Is there a better way to do this?

推荐答案

您需要一个快速的数据结构，它可以添加，删除和查询的最大元素小于O（n）时间（你可以用一个数组，如果为O（n）或O（nlogn）是可以接受的）。您可以使用一个堆，平衡二叉搜索树，跳跃列表，或任何其他排序的数据结构，在O的执行这些操作（的log（n））。

You need a fast data structure that can add, remove and query for the max element in less than O(n) time (you can just use an array if O(n) or O(nlogn) is acceptable). You can use a heap, a balanced binary search tree, a skip list, or any other sorted data structure that performs these operations in O(log(n)).

好消息是，最流行的语言都实现了一个排序的数据结构支持这些操作为您服务。 C ++有的std ::设为和的std :: multiset的（你可能需要后者）和Java具有 TreeSet的。

The good news is that most popular languages have a sorted data structure implemented that supports these operations for you. C++ has std::set and std::multiset (you probably need the latter) and Java has TreeSet.

这篇关于在数组中发现的最大尺寸为k的每个窗口的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！