NextGreaterElementIIOPT2 [source code]

public class NextGreaterElementIIOPT2 {
    public int[] nextGreaterElements(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];
        int maxIndex = 0;
        for (int i = 0; i < nums.length; i++) if (nums[i] > nums[maxIndex])  maxIndex = i;          //find the largest element

        int[] index = new int[nums.length];         //declare an array that holds the index of next greater element
        index[maxIndex] = -1;     //set the max element's value to -1
        for (int i = (maxIndex - 1 + nums.length) % nums.length; i != maxIndex; i = (i - 1 + nums.length) % nums.length) {     //the array is circular. pay attention to 'i'
            if (nums[i] < nums[(i + 1) % nums.length]) {
                index[i] = (i + 1) % nums.length;         //set index[i] = (i+1)%nums.length if nums[(i+1)%nums.length]>nums[i]
            } else {
                int res = index[(i + 1 + nums.length) % nums.length];         //res = index of the cloest element whose value greater than nums[(i+1)%nums.length]
                while (res != -1 && index[res] != -1 && nums[i] >= nums[res]) res = index[res];         //find the closet index makes nums[index] > nums[i]. if nums[i] >= nums[res], try nums[index[res]], index[res] is the index of the closest element whose value is greater than nums[res]. repeat the process until we find such an element. 
                if (res != -1 && nums[res] == nums[i]) res = -1;    //res==-1 or index[res]==-1 means current element is another largest element, just set index[i] = -1.
                index[i] = res;
            }
        }
        int[] result = new int[nums.length];         // retrieve value with index recorded previously
        for (int i = 0; i < result.length; i++) result[i] = index[i] != -1 ? nums[index[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};
        int[] input5 = {5,4,3,2,1};
        int[] input6 = {1,1,1,1,1};
        NextGreaterElementIIOPT2 tester = new NextGreaterElementIIOPT2();
        for (int i : tester.nextGreaterElements(input6)) System.out.println(i);
    }
}

这个是21ms, 99.71%,更加快的一个算法;

这个是作者的解释:
summary:
find first occurance of the greatest element, set maxIndex= its index.

declare an array holds the index of next greater element, set index[maxIndex]=-1.Then calculate each the other elements from right to left.
Assuming we're calculating index[i], so we've calculated index[i+1], index[i+2].... There're two situations:

1. nums[i]<nums[i+1]. Just set index[i] = i+1 (leave alone mod operations...)
2. nums[i] >= nums[i+1]. We already known that the next element whose value greater than nums[i+1] stored in index[i+1], we can retrieve
   that greater value and compare to see if it is greater than nums[i]. If so, set index[i] = index[i+1]. Otherwise, repeat the process.
   (Proof: nums[i]>nums[i+1] and the closest greater element locates in nums[index[i+1]], so elements between nums[i+1]...nums[index[i+1]-1]
   are smaller than nums[i+1] so smaller than nums[i] appearantly, so we don't have to compare them one by one in linear search, which skips
   serval elements and makes the algorithm more efficient.) Then declare another array to store the result, loop and set result[i]=nums[index[i]]

这个算法是一个完全不同的思路, 不是利用decreasing subsequence的思路来做了, 完成加速的核心也不是依靠重新实现 stack(无论是用 list 还是 array, 这些加速不能说trivial, 但是并不是很 innovative). 而是依靠重新设计了一个算法;

for (int i = (maxIndex - 1 + nums.length) % nums.length; i != maxIndex; i = (i - 1 + nums.length) % nums.length)

这个 header 刚开始看可能有点不理解, 其实这个可以理解为circular traversal里面的一个常规操作了. +nums.length之后再 mod 是为了避免负值fall off the left edge;
可以看到后面 nums[(i + 1) % nums.length 这样的代码的是偶
这个 header 整体完成的内容很简单, 就是从 maxIndex 开始, 往左边走, 直到走一圈; 注意这里i 的范围始终是在0..nums.length-1以内的;

while (res != -1 && index[res] != -1 && nums[i] >= nums[res]) {    
    res = index[res];      
}

这个步骤是很聪明的. 首先刚开始可能看不懂, 是因为这里 index 这个名字不好. 其实index[i]就是index of next greater element of nums[i];
这个步骤完成的是一个跳子的操作, 因为我们要照的是NGE of nums[i], 所以直接只按照一个 incresing 的顺序找就行了, 这个increasing search的完成就是依靠利用右边已经计算好的结果. 这样一个跳子查找给加速做了很大的贡献;

这个算法整体真的是一个非常巧妙的算法, 无论是整体的设计思路(利用了一种 induction 的思维方法, 这个也是我希望训练的一个思维方法, 但是很难), 还是loop 的细节上的处理, 还是boundary case的处理, 都很完美;

有一个小细节: 刚开始不理解为什么要加res != -1这个判断, 感觉永远不会到这一步(到了index[res]==-1按说就应该停止了). 但是实际上如果是碰到i and i+1都是最大值的情况, 比如1,1,1这个 case,那么就有可能会到达res==-1的情况. 如果是1,1,0这个 case, 就不会触发这个情况, 自己想想为什么.

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