从数组A构造数组B，每个索引都是原始数组中第k个元素的最大值

Question

给定数组A，长度n和一个自然数k，使得1 <= k <= n。构造一个满足以下条件的B大小的数组n-k+1 -每个B[j]都是A[j],A[j+1],...A[j+k-1]之间的最大值

假设在线性时间内求解。例如：

A = {3,1,5,12,13,4,2} size 7 and k = 3. desired answer would be -
B = {5,12,13,13,13}

注意:这不是一个家庭作业问题，而是我有困难解决的考试后问题。

尝试使用最多包含k个元素的双端队列，但我在跟踪第k个最大值时遇到问题。

Answer 1

这通常是一个单调的队列问题。

这里有一个关于它的描述。读一读它，它很容易！

https://leetcode.com/problems/sliding-window-maximum/discuss/65885/this-is-a-typical-monotonic-queue-problem

Answer 2

我认为这将是有帮助的：https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/。第三种解决方案是使用双队列来跟踪k个元素的窗口中的最大元素。复杂度将为O(n)。