NextGreaterElementIIOPT4 [source code]

public class NextGreaterElementIIOPT4 {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        if(n == 0) return res;
        int max = nums[0], index = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] > max) {
                res[i - 1] = i;
                res[index] = i;
                max = nums[i];
                index = i;
            }
        }
        res[index] = -1;
        for (int i = index - 1; i > index - n; i--) {
            int real = (i + n) % n;
            if (res[real] != 0) continue;
            res[real] = real == n - 1 ? 0 : real + 1;
            while (res[real] != -1 && nums[real] >= nums[res[real]]) res[real] = res[res[real]];
        }
        for (int i = 0; i < n; i++) if (res[i] != -1) res[i] = nums[res[i]]; 
        return res;
    }

    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};
        int[] input5 = {1,1,1,1,1};
        NextGreaterElementIIOPT4 tester = new NextGreaterElementIIOPT4();
        for (int i : tester.nextGreaterElements(input5)) System.out.println(i);
    }
}

这个是22ms,更加快的一个算法;

第一个 loop 还是常规的初始化, 只不过有一定的优化: 每一个新晋的 max, 都自动成为自己 predecessor 的NGE, 同是成为上一任 max 的 NGE.
需要注意的是, 这里计算出来的几个 res 值, 全都是 final 的,也就是肯定最后是正确的, 所以在下面第二个循环的 continue 语句对这些进行了
判断; 比如1,2,1,3,1,4, 我们第一个循环跑完之后有: 1, 3, 3, 5, 5, -1; 像这里这个是一个特殊情况, 直接第一个循环结束所有的都有结果了,
而且这个结果是 final 的;

       for (int i = index - 1; i > index - n; i--) {  
            int real = (i + n) % n;

可以看到, 处理 circular 的方法其实很多, 这里又是一种. 看起来好像index - n出界了,但是这里只是在 header 里面, 没有什么出界的说法!
只要你最后用来 index 的时候使用的都是 real, which can never be out of bound, 那么 i 本身多大还是多小, 都完全没有关系;

后面的内容其实都比较直观, 总体的思路跟 OPT2的思路很类似, 使用的也是一个从右向左的扫描, 同时使用了跳子的思路; 比如把res[real]先初始化到real+1, 然后用跳子进行一个2pass, 这个跟 opt2的思路几乎是一样的, 不过写法其实更简洁; 简洁在哪里?如果你深刻理解了 opt2和 opt4的代码, 你就能看到其实核心上, 这两种代码是对res[real]是否等于real+1的情况进行了不同的处理方式. 虽然肯定是要用一个 conditional, 但是具体的处理方式不一样:

1. opt2里面, 用的是if else的处理方式, 这个是最直接的;
2. opt4里面, 用的是一个类似conditional override的思路: 先全都设置到real+1, 然后conditional update 2pass.

最后的这个 while 循环其实包含了深厚的逻辑. 可以注意的是, 像1,1,1,1,1这样的boundary case, 在 opt4里面就不需要单独
处理了;

这个代码总体还是很不错的, 另外NGEII 这个问题总算是告一段落了, 总结一下几个代码里面都碰到过的一些技巧(可能是通用于 array问题的):

1. index 与 value 分离. 虽然有些代码选择了直接把res[real]更新成 value, 但是很多代码的做法还是先在 loop 里面把 NGE 的index 放到res[real]里面, 然后最后就算单独来一个1pass, 其实也是非常快的;
2. while loop 的 header, 尤其是里面有好几个 condition 的时候, 往往有至少一个是terminating condition. 读的时候不要看到太多并列的 condition 就紧张, 挑出大概感觉是terminating condition的几个, 暂时不看就行了.

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