0

Given array A, length n and a natural number k such that 1 <= k <= n. Construct an array B size n-k+1 that suffices the following - every B[j] is the max between A[j],A[j+1],...A[j+k-1]

suppose to solve in linear time. for example:

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

Note; this is not a homework question, but post exam question that I'm having trouble to solve.

Tried using Double-Ended Queue that will contain at the max k elements, but I'm having a problem tracking the kth maximum.

BOB123
  • 176
  • 10
  • What problem have you got with Double-Ended Queue? [Look here](https://stackoverflow.com/questions/12190184/can-min-max-of-moving-window-achieve-in-on/12195098#12195098) – MBo Jul 08 '19 at 07:49

2 Answers2

0

This is typically a monotonous queue problem.

Here is a description about it. Read it and it is easy!

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

Faruk Hossain
  • 1,205
  • 5
  • 12
0

I think this will be helpful: https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/. The third solution is using a deque to track the maximum element in the windows of k elements. Complexity will be O(n).

Tùng Lưu
  • 1
  • 1