查找数组中每个大小为 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::set 和 std::multiset(你可能需要后者)，Java 有 PriorityQueue 和 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 PriorityQueue and TreeSet.

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