Count bounded slices 2 – O(n) solution

This is the O(n) solution, without result permutation output. Thanks to the answer from careerup link. I wrote my understanding and analysis.
The basic idea is that we start with arr[0] and then see how many more elements you can include before you violate the max-min<=k constraint. When it reaches some index ‘end’ you can no longer include, you know the maximum subarray starting at index 0 is arr[0…end-1], and you can count ‘end’ different subarrays there. You then already know arr[1…end-1] is valid, and you try to advance the right boundary again (try arr[1…end], then arr[1…end+1]) and so on until again you reach a point ‘front’ past which you can’t advance. Then you’ll try subarrays starting with index 2, and so on.
In order to simplify the output, I just output the range of subarrays. The final result are the permutation of them. If we consider about result output, it may take more than O(n) time.
Let’s take following example:



My code:

1. import java.util.ArrayList;
2. public class CountBoundedSlices2 {
3.     public static void main(String[] args) {
4.         int[] arr = {1, 3, 2, 4, 5, 1, 6, 7, 9};
5.         countBoundedSlices(arr, 4);
6.     }
8.     public static void countBoundedSlices(int[] arr, int k){
9.         //initial maxQueue and minQueue.
10.         int front=0, end=1;
11.         BoundedSlicesSData frontElem = new BoundedSlicesSData(arr[front],front);
12.         BoundedSlicesSData endElem = new BoundedSlicesSData(arr[end],end);
13.         ArrayList < BoundedSlicesSData> maxQueue = new ArrayList< BoundedSlicesSData>();
14.         ArrayList < BoundedSlicesSData> minQueue = new ArrayList< BoundedSlicesSData>();
15.         addToMaxQueue(maxQueue, frontElem);
16.         addToMaxQueue(maxQueue, endElem);
17.         addToMinQueue(minQueue, frontElem);
18.         addToMinQueue(minQueue, endElem);
19.         //The following elements are recorded to check max-min < k
20.         BoundedSlicesSData maxElem = maxQueue.get(0);    //indicate the max element.
21.         BoundedSlicesSData minElem = minQueue.get(0);    //indicate the min element.
22.         for(;front < arr.length&&end+1 < arr.length;front++){
23.             //delete elements from front which has position less than front.
24.             while(maxElem.position < front){
25.                 maxQueue.remove(0);
26.                 maxElem = maxQueue.get(0);
27.             }
28.             while(minElem.position < front){
29.                 minQueue.remove(0);
30.                 minElem = minQueue.get(0);
31.             }
32.             //move end forward until max-min < k
33.             while(front < arr.length&&end+1 < arr.length&&((maxElem.value-minElem.value < k)||front==end)){
34.                 end++;
35.                 endElem = new BoundedSlicesSData(arr[end], end);
36.                 addToMaxQueue(maxQueue, endElem);
37.                 addToMinQueue(minQueue, endElem);
38.                 maxElem = maxQueue.get(0);
39.                 minElem = minQueue.get(0);
40.             }
41.             if(front!=end-1){
42.                 System.out.println(“(“+front+”,”+(end-1)+”)”);
43.             }
44.             if(end==arr.length-1){    //to get the last result
45.                 System.out.println(“(“+front+”,”+end+”)”);
46.             }
47.         }
48.     }
50.     /*
51.      * Add a new element to min queue. Keep the min quene with ascend sequence.
52.      */
53.     public static void addToMinQueue(ArrayList < BoundedSlicesSData> queue, BoundedSlicesSData newElement){
54.         if(queue.size()==0){
55.             queue.add(newElement);
56.             return;
57.         }
58.         BoundedSlicesSData front = queue.get(0);
59.         if(newElement.value < front.value){    //new element is smaller than the front. Clear queue and add it.
60.             queue.clear();
61.             queue.add(newElement);
62.             return;
63.         }
64.         BoundedSlicesSData end = queue.get(queue.size()-1);
65.          /* Or delete those elements which are larger than new element from end of queue.
66.          * And add new element to the queue. */
67.         while(end.value>=newElement.value){
68.             queue.remove(queue.size()-1);
69.             end = queue.get(queue.size()-1);
70.         }
71.         queue.add(newElement);
72.     }
74.     /*
75.      * Add a new element to max queue. Keep the min quene with descend sequence.
76.      */
77.     public static void addToMaxQueue(ArrayList < BoundedSlicesSData> queue, BoundedSlicesSData newElement){
78.         if(queue.size()==0){
79.             queue.add(newElement);
80.             return;
81.         }
82.         BoundedSlicesSData front = queue.get(0);
83.         if(newElement.value>front.value){    //new element is larger than the front. Clear queue and add it.
84.             queue.clear();
85.             queue.add(newElement);
86.             return;
87.         }
88.         BoundedSlicesSData end = queue.get(queue.size()-1);
89.          /* Or delete those elements which are less than new element from end of queue.
90.          * And add new element to the queue. */
91.         while(end.value < =newElement.value){
92.             queue.remove(queue.size()-1);
93.             end = queue.get(queue.size()-1);
94.         }
95.         queue.add(newElement);
96.     }
98. }
99. /*
100.  * The queue should store both value and position. So create this class for convinent.
101.  */
102. class BoundedSlicesSData{
103.     int value;
104.     int position;
105.     public BoundedSlicesSData(){}
106.     public BoundedSlicesSData(int value, int position){
107.         this.value = value;
108.         this.position = position;
109.     }
110. }