-
Notifications
You must be signed in to change notification settings - Fork 25
/
Maximum_of_all_subarrays_of_size_k.java
70 lines (57 loc) · 1.7 KB
/
Maximum_of_all_subarrays_of_size_k.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// { Driver Code Starts
//Initial template for JAVA
import java.util.*;
import java.io.*;
import java.lang.*;
class Main {
public static void main(String args[]) {
// taking input using class Scanner
Scanner sc = new Scanner(System.in);
// taking total count of testcases
int t = sc.nextInt();
while (t-- > 0) {
// taking total number of elements
int n = sc.nextInt();
// taking size of subArrays
int k = sc.nextInt();
// Declaring and Intializing an array of size n
int arr[] = new int[n];
// adding all the elements to the array
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// Calling the method max_of_subarrays of class solve
// and storing the result in an ArrayList
ArrayList<Integer> res = new Solution().max_of_subarrays(arr, n, k);
// printing the elements of the ArrayList
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
System.out.println();
}
}
}// } Driver Code Ends
// User function template for JAVA
class Solution {
static ArrayList<Integer> max_of_subarrays(int arr[], int n, int k) {
ArrayList<Integer> ans = new ArrayList<>();
Deque<Integer> q = new LinkedList<>();
for (int i = 0; i < k; i++) {
while (!q.isEmpty() && arr[i] >= arr[q.peekLast()]) {
q.removeLast();
}
q.addLast(i);
}
for (int i = k; i < n; i++) {
ans.add(arr[q.peek()]);
while (!q.isEmpty() && q.peek() <= i - k) {
q.removeFirst();
}
while (!q.isEmpty() && arr[i] >= arr[q.peekLast()]) {
q.removeLast();
}
q.addLast(i);
}
ans.add(arr[q.peek()]);
return ans;
}
}