fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	// public static void main(String[] args) {
  11.  
  12.  
  13.  //       int arr[]={1,3,-1,-3,5,3,6,7};
  14.  //       int k=3;
  15.  //       int l=0,r=3-l-1;
  16.  //       List<Integer> min =new ArrayList<>();
  17.  //       List<Integer> max =new ArrayList<>();
  18.  //       while(l < arr.length && r< arr.length){
  19.  //           Deque<Integer> dq = designIncresingQueue(arr,l,r);
  20.  //           Deque<Integer> dq2 = designDecresingQueue(arr,l,r);
  21.  //           r++;
  22.  //           l++;
  23.  //           min.add(arr[dq.peekFirst()]);
  24.  //           max.add(arr[dq2.peekFirst()]);
  25.  //       }
  26.  //       System.out.println(min);
  27.  //       System.out.println(max);
  28.  //   }
  29.  
  30.    public static void main(String[] args) {
  31.         int[] arr = {1,3,-1,-3,5,3,6,7};
  32.         int k = 3; // window size
  33.  
  34.         List<Integer> min = new ArrayList<>();
  35.         List<Integer> max = new ArrayList<>();
  36.  
  37.         Deque<Integer> minDq = new ArrayDeque<>();
  38.         Deque<Integer> maxDq = new ArrayDeque<>();
  39.  
  40.         int l = 0;
  41.  
  42.         for (int r = 0; r < arr.length; r++) {
  43.  
  44.             // maintain increasing deque (min)
  45.             while (!minDq.isEmpty() && arr[minDq.peekLast()] > arr[r]) {
  46.                 minDq.pollLast();
  47.             }
  48.             minDq.addLast(r);
  49.  
  50.             // maintain decreasing deque (max)
  51.             while (!maxDq.isEmpty() && arr[maxDq.peekLast()] < arr[r]) {
  52.                 maxDq.pollLast();
  53.             }
  54.             maxDq.addLast(r);
  55.  
  56.             // window size reached
  57.             if (r - l + 1 == k) {
  58.  
  59.                 min.add(arr[minDq.peekFirst()]);
  60.                 max.add(arr[maxDq.peekFirst()]);
  61.  
  62.                 // remove out of window
  63.                 if (minDq.peekFirst() == l) {
  64.                     minDq.pollFirst();
  65.                 }
  66.                 if (maxDq.peekFirst() == l) {
  67.                     maxDq.pollFirst();
  68.                 }
  69.  
  70.                 l++;
  71.             }
  72.         }
  73.  
  74.         System.out.println("Min: " + min);
  75.         System.out.println("Max: " + max);
  76.     }
  77.  
  78.     public static  Deque<Integer> designIncresingQueue(int []arr,int start,int end){
  79.         Deque<Integer> dq = new ArrayDeque<>();
  80.         for(int i=start;i<=end;i++){
  81.             while(!dq.isEmpty() && arr[dq.peekLast()] > arr[i]){
  82.                 dq.pollLast();
  83.             }
  84.             dq.offerLast(i);
  85.         }
  86.         return dq;
  87.     }
  88.  
  89.     public static  Deque<Integer> designDecresingQueue(int []arr,int start,int end){
  90.         Deque<Integer> dq = new ArrayDeque<>();
  91.         for(int i=start;i<=end;i++){
  92.             while(!dq.isEmpty() && arr[dq.peekLast()] < arr[i]){
  93.                 dq.pollLast();
  94.             }
  95.             dq.offerLast(i);
  96.         }
  97.         return dq;
  98.     }
  99. }
Success #stdin #stdout 0.1s 55380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Min: [-1, -3, -3, -3, 3, 3]
Max: [3, 3, 5, 5, 6, 7]
https://ideone.com/7lLKw0
language:
Java (HotSpot 12)
created:
22 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!