Count bounded slices

Problem:
Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= k. Pair of indices shouldn’t be like (i,i).
Consider k is 2. And the array is 3 5 7 6 3.
Output: (0,1) (1,2) (1,3) (2,3)

Analysis:
A brute-force idea is to recursively find max/min of all indices. Once finding the max/min, output the result. And use hashmap store the history results to reduce duplicate calculation. Because it iterates all possible indices, the time/space complexity is optimized.
This idea is to maintain a ascend queue. Queue front stores the min value. Queue end stores the max valule. Each time, add new element into the sorted queue. Check the max-min. If it is smaller than k, print the results with new element. If max-min is greater than k, we need to adjust the queue before print the results.
It is similar to max value in a sliding widow. But the difference is that in this case, the queue maintain both min value in the front, max value in the end. And max in sliding window only store a max value(or min value).
I provide the following process for understanding:


There are N elements. For each element, it takes O(logn) to insert into the queue, and O(n) to output the result. So the total time complexity is O(n*(n+logn)), which is O(n^2). Not considering result output, it is O(nlogn).
Complete code is following:

1. import java.util.ArrayList;
2. import java.util.Collections;
3. import java.util.Comparator;
4. public class CountBoundedSlices {
5.     public static void main(String[] args) {
6.         int[] arr = {1, 3, 2, 4, 5, 1, 6, 7, 9};
7.         countBoundedSlices(arr, 2);
8.     }
10.     public static void countBoundedSlices(int[] arr, int k){
11.         BoundedSlicesSData curr = new BoundedSlicesSData(arr[0],0);
12.         ArrayList queue = new ArrayList();
13.         queue.add(curr);
14.         for(int i=1;i < arr.length;i++){
15.             curr = new BoundedSlicesSData(arr[i], i);
16.             queue.add(curr);
17.             Collections.sort(queue, new BoundedSlicesSDataComparator());    //add current element into queue.
18.             BoundedSlicesSData front = queue.get(0);
19.             BoundedSlicesSData end = queue.get(queue.size()-1);
20.             if(end.value-front.value>k&&curr.value==end.value){
21.                 //Got a larger value at queue end. It makes max-min>k. So modify the queue front.
22.                 while(end.value-front.value>k){
23.                     int front_time = front.position;
24.                     queue.remove(0);
25.                     front = queue.get(0);
26.                     while(front.position < front_time){    //delete those elements, which are earlier inserted than front
27.                         queue.remove(0);
28.                         front = queue.get(0);
29.                     }//while
30.                 }//while
31.                 for(int j=0;j < queue.size()-1;j++){
32.                     printResult(queue.get(j).position, end.position);
33.                 }
34.             }
35.             else if(end.value-front.value>k&&curr.value==front.value){
36.                 //Got a smaller value at queue front. It makes max-min>k. So modify the queue end.
37.                 while(end.value-front.value>k){
38.                     int end_time = end.position;
39.                     queue.remove(queue.size()-1);
40.                     end = queue.get(queue.size()-1);
41.                     while(end.position < end_time){    //delete those elements, which are earlier inserted than front
42.                         queue.remove(queue.size()-1);
43.                         end = queue.get(queue.size()-1);
44.                     }//while
45.                 }//while
46.                 for(int j=queue.size()-1;j>0;j–){
47.                     printResult(queue.get(j).position, front.position);
48.                 }
49.             }//if
50.             else{
51.                 //insertation of curr doesn’t affect max, min. Print result with curr
52.                 for(int j=0;j < queue.size();j++){
53.                     BoundedSlicesSData printAux = queue.get(j);
54.                     if(printAux.position==curr.position){
55.                         continue;
56.                     }
57.                     printResult(printAux.position, curr.position);
58.                 }
59.             }//if
60.         }//for
61.     }
63.     public static void printResult(int i, int j){
64.         if(i < j){
65.             System.out.println(“(“+i+”,”+j+”)”);
66.         }
67.         else{
68.             System.out.println(“(“+j+”,”+i+”)”);
69.         }
70.     }
71. }
72. /*
73.  * The queue should store both value and position. So create this class for convinent.
74.  */
75. class BoundedSlicesSData{
76.     int value;
77.     int position;
78.     public BoundedSlicesSData(){}
79.     public BoundedSlicesSData(int value, int position){
80.         this.value = value;
81.         this.position = position;
82.     }
83. }
84. /*
85.  * help to sort the BoundedSlicesSData queue
86.  */
87. class BoundedSlicesSDataComparator implements Comparator < BoundedSlicesSData>{
88.     public int compare(BoundedSlicesSData b1, BoundedSlicesSData b2){
89.         return b1.value – b2.value;
90.     }
91. }