NEXT GREATEST ELEMENT: For each element of input array, it finds the next bigger-than-itself element in that array; -1 if no greater element is present.

console.md

Console Output for following code:

Input : [1, 4, 9, 8, 7, 5, 4]
Output: [4, 9, -1, -1, -1, -1, -1]
Input : [4, 3, 7, 2, 9, 1, 8]
Output: [7, 7, 9, 9, -1, 8, -1]
Input : [4, 4, 5, 2, 6, 6, 1]
Output: [5, 5, 6, 6, -1, -1, -1]

Process finished with exit code 0

NextGreatestElement.java

import java.util.Arrays;
import java.util.Stack;

/**
 * Created by Abhishek Anand on 24-Oct-17.
 */

/*
Finds the next greatest element for each element in an array. -1 if no greater element is present.
 */
public class NextGreatestElement {
    public static int[] getGreatestArray(int[] input) {
        Stack<Integer> stack = new Stack<>();
        int output[] = new int[input.length];
        for (int i = input.length - 1; i >= 0; i--) {
            if (stack.isEmpty()) {
                output[i] = -1;

            } else if (stack.peek() > input[i]) {
                output[i] = stack.peek();
            } else {
                while (!stack.isEmpty() && stack.peek() <= input[i]) {
                    stack.pop();
                }
                if (stack.isEmpty()) {
                    output[i] = -1;
                } else {
                    output[i] = stack.peek();
                }
            }
            stack.push(input[i]);
//            System.out.println(stack.peek());
        }
        return output;
    }

    public static void main(String args[]) {
        int[] arr;
        arr = new int[]{1, 4, 9, 8, 7, 5, 4};
        System.out.println("Input : " + Arrays.toString(arr));
        System.out.println("Output: " + Arrays.toString(getGreatestArray(arr)));

        arr = new int[]{4, 3, 7, 2, 9, 1, 8};
        System.out.println("Input : " + Arrays.toString(arr));
        System.out.println("Output: " + Arrays.toString(getGreatestArray(arr)));

        arr = new int[]{4, 4, 5, 2, 6, 6, 1};
        System.out.println("Input : " + Arrays.toString(arr));
        System.out.println("Output: " + Arrays.toString(getGreatestArray(arr)));
    }
}