Surpasser Count of each element in an array

Given an array of distinct integers, for each element of the array count the number of elements to the right that are greater than that element.

A surpasser of an element of an array is a greater element to its right, therefore x[j] is a surpasser of x[i] if i < j and x[i] < x[j].

Example:

input = [6, 5, 4, 7, 2, 8, 0]

output= [2, 2, 2, 1, 1, 0, 0]

Approach 1:

Simplest approach to iterate every time throught the array and find out greater element to it's right. This approach would require O(n^2) complexity and no space complexity.

Approach 2:

We can use O(n)  extra space and solve this efficiently. Priority queue can be used here to store the element in sorted order so that we can check the number of greater element in faster manner. So the complexity will be similar to the time required to push element to priority queue and removing from the same to check for greater element.

Steps:

Start from rear end of array, pick one element each time

Check if queue head is greater than current element 
if yes means all the element in queue are greater than current element.

Save the size of queue as output for specific index of input array

if no then remove element from queue and store it to stack for temporaty storage.
Go to step 1 again



Approach 2 is implemented in solution below.

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class SurpasserCount {
    public static void main(String[] args) {
        int[]  input = {6, 5, 4, 7, 2, 8, 0};
        int[] output = new int[input.length];

        Queue queue = new PriorityQueue();
        Stack stack = new Stack();

        for ( int i = input.length -1; i >= 0; i-- ){
            while (!queue.isEmpty()) {
                if (queue.peek() > input[i]) {
                    output[i] = queue.size();
                    break;
                } else {
                    stack.push(queue.remove());
                }
            }
            if (queue.isEmpty())
                output[i]=0;

            while (!stack.isEmpty()){
                queue.add(stack.pop());
            }

            queue.add(input[i]);
        }

        for (int i: output) {
            System.out.print(i + " ");
        }
    }
}
 

Comments are welcome.
Problem Source