Stack & Queues - Min Max Riddle [M]

 

Sample Input 0

4

2 6 1 12

Sample Output 0

12 2 1 1

Explanation 0

Here  and 

window size	window1	window2	window3	window4	maximum of all windows
1	2	6	1	12	12
2	2	1	1		2
3	1	1			1
4	1				1

 static long[] riddle(long[] arr) {

        // complete this function

       int n=arr.length;

       Stack<Integer> st=new Stack<>();

       int[] left=new int[n+1];

       int[] right=new int[n+1];

       for(int i=0;i<n;i++){

           left[i]=-1;

           right[i]=n;

       }

       for(int i=0;i<n;i++){

           while(!st.isEmpty() && arr[st.peek()]>=arr[i])

               st.pop();

           

           if(!st.isEmpty())

               left[i]=st.peek();

           

           st.push(i);

       }

       while(!st.isEmpty()){

           st.pop();

       }

       for(int i=n-1;i>=0;i--){

           while(!st.isEmpty() && arr[st.peek()]>=arr[i])

               st.pop();

           

           if(!st.isEmpty())

               right[i]=st.peek();

           

           st.push(i);

       }

        long ans[] = new long[n+1]; 

        for (int i=0; i<=n; i++) {

            ans[i] = 0; 

        }

         for (int i=0; i<n; i++) 

        { 

            int len = right[i] - left[i] - 1; 

            ans[len] = Math.max(ans[len], arr[i]); 

        }

        for (int i=n-1; i>=1; i--) {

            ans[i] = Math.max(ans[i], ans[i+1]);  

        }

       long[] res=new long[n];

        for (int i=1; i<=n; i++) {

            res[i-1]=ans[i];

        }

        return res;

    }