Next Greater Element II

Problem

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.

Solution

public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];
        int len = nums.length;
        int[] res = new int[len];
        int max = Arrays.stream(nums).max().getAsInt(); //max() will return OptionInt, Java 8 new feature 
        for (int i = 0; i < len; i++) {
            if (nums[i] == max) {
                res[i] = -1;
                continue;
            }
            for (int j = i + 1; i != j; j++) { //Start from the next element i + 1
                if (j == len) j = 0;
                if (nums[j] > nums[i]) {
                    res[i] = nums[j];
                    break;
                }
            }
        }
        return res;
    }
}

Analysis

The difference between this problem and Next Greater Element I is that we have only one array, which can be searched in circular
We know that only max number cannot be found the greater element, hence we first get it by calling:
Arrays.stream(nums).max().getAsInt()
Then we use two loops to find the required element
We start from the next element inside second loop as init j = i + 1
If we reach the end, we start it again from the start, which is if (j == len) j = 0;