给定大小为n和k的数组，您如何找到大小为k的每个连续子数组的最大值？
例如
arr = 1 5 2 6 3 1 24 7 k = 3 ans = 5 6 6 6 24 24
我正在考虑使用大小为k的数组，并且每个步骤都将最后一个元素逐出，并添加新元素并在其中找到最大值。这导致运行时间为O（nk）。有一个更好的方法吗？
您需要一种快速的数据结构，可以在不到O（n）的时间内添加，删除和查询max元素（如果可以接受O（n）或O（nlogn），则可以使用数组）。您可以使用堆，平衡的二进制搜索树，跳过列表或在O（log（n））中执行这些操作的任何其他排序数据结构。
好消息是，大多数流行语言都实现了已排序的数据结构，可以为您支持这些操作。C ++具有std::set和std::multiset（您可能需要后者），而Java具有TreeSet。
std::set
std::multiset
TreeSet
