NextGreaterElementIIOPT [source code]

public class NextGreaterElementIIOPT {
    public int[] nextGreaterElements(int[] nums) {
        int[] r = new int[nums.length];
        if (nums.length == 0) return r;
        Arrays.fill(r, -1);
        int[] N = new int[nums.length];
        int[] P = new int[nums.length]; 
        N[0] = nums[0];
        P[0] = 0;
        int p = 0, l = 2 * r.length;
        for (int i = 1; i < l - 1; ++i) {
            int ri = i % r.length;
            if (nums[ri] <= N[p]) {
                if (++p >= r.length) break;
                N[p] = nums[ri];
                P[p] = ri;
            } else {
                while (p >= 0 && N[p] < nums[ri]) r[P[p--]] = nums[ri];
                N[++p] = nums[ri];
                P[p] = ri;
            }
        }
        return r;
    }

    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};
        NextGreaterElementIIOPT tester = new NextGreaterElementIIOPT();
        for (int i : tester.nextGreaterElements(input3)) System.out.println(i);
    }
}

这个是看来的答案, 时间27ms, 98%, 最优解.

这个算法首先要学习的一点就是++和--的用法: 在简化代码的角度来说, 这个东西其实是很好理解的:

if (++p >= r.length) break;

其实就等于

p++;  
if (p >= r.length) break;

同样的,

r[P[p--]] = nums[ri];

就相当于

{  
    r[P[p]] = nums[ri];  
    p--;  
}

可以看到, ++和--运算符的使用其实非常直接, 就是减少一行代码而已, 完全没有什么神奇的地方;
更进一步:

                N[++p] = nums[ri];  
                P[p] = ri;

里面 N 和 P 的 index 是一样的! 不要因为看到写的代码不 identical 就潜意识感觉不一样, 其实这两个 index 的pointer 是统一的;

不过话说回来, 这样的 compact 的++和--的应用在第一遍代码的时候真的不要过分纠结, 就写做简单的方式来写就行了, 最后优化的时候才考虑去替换这些东西, premature optimization is the root of all evil;

                while (p >= 0 && N[p] < nums[ri]) r[P[p--]] = nums[ri];  
                N[++p] = nums[ri];

这里要有一个++是因为上面这个 loop 结束之后, p 一定是-1.

另外这个算法的本质其实是比较直观的, 就是用两个 array 来模拟 Stack 的操作, 这个其实还是一个很聪明的想法, 对于速度的提升也是很直观的. 值得学习.

在用 trace 模拟思考的时候, 我们前面也讲过, 还是可以用3,2,1,4这样的简单的例子来帮助思考作为开始.

值得注意的是, 在while 完成之后, p 重新指向两个 array 的开头, 这个时候你是不用故意把后面的 element 全都清空的, 因为反正到时候更新的时候就会自动的被 override 了;

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