NextGreaterElementII [source code]

public class NextGreaterElementII {
    public int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            for (; j < i + nums.length; j++) {
                if (nums[j % nums.length] > nums[i]) {
                    result[i] = nums[j % nums.length];
                    break;
                }
            }
            if (j == i + nums.length) result[i] = -1;

        }
        return result;
    }

    public static void main(String[] arg) {
        int[] input1 = {1,2,1};
        int[] input2 = {1,3,4,5,2};
        int[] input3 = {100,1,11,1,120,111,123,1,-1,-100};
        int[] input4 = {1,2,1,3,1,4,1,5,1,6};
        NextGreaterElementII tester = new NextGreaterElementII();
        for (int i : tester.nextGreaterElements(input3)) System.out.println(i);
    }
}

failed case 1:
Input:
[100,1, 11, 1, 120,111,123,1, -1, -100]
Output:
[120,120,120,120,123,123,-1,120,100,100]
Expected:
[120,11,120,120,123,123,-1, 100,100,100]
这一题跟前面那题不一样,这一题允许重复,直接用一个 map 来做就不行了.

暂时想不到什么特别好的办法,先做这个暴力解. 这个解想法还是比较简单的,n^2复杂度,而且没有做到inplace return.
唯一需要注意一点的一个小窍门就是 j 的声明要在 j 的 forloop 的外面,这样可以用来后面 loop 完了之后判断termination condition,也就是"没有找到"的情况.
刚开始想过给 result 一个特殊的初始值,然后最后用这个来判断"没有找到"的情况,不过这个其实相对就复杂一点了. 而且用什么初始值好呢? 因为这里是一个数字问题 ,所以你用的,比如0,这种,全都有可能出现在 input 里面;所以这个就很麻烦. 直接用这个方法更好一些,而且这个方法其实我也挺熟悉的了.

Problem Description

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.
Note: The length of given array won't exceed 10000.

Subscribe to see which companies asked this question.

Hide Tags Stack
Hide Similar Problems (E) Next Greater Element I