You are given an integer array of size N. Assume a sliding window of size k starting from index 0. In each iteration, the sliding window moves to the right by one position till N-k. Write a program to return an array representing the maximum number in all sliding windows.

Problem Note

  • The first element of the answer array is max (A[0...k]), then the second element is max (A[1...k+1]) and so on.
  • The size of the answer array will be N-k+1.
  • You are expected to solve this question in O(n) time complexity

Example 1

Input: A[] = [4,3,8,9,0,1], k = 3
Output: [8,9,9,9]

Example 2

Input: A[] = [9,8,6,4,3,1], k = 4
Output: [9,8,6]

Example 3

Input: A[] = [1,2,3,4,10,6,9,8,7,5], k = 3
Output: [3,4,10,10,10,9,9,8]