NextGreaterElementIIOPT3 [source code]

public class NextGreaterElementIIOPT3 {
    public static int[] nextGreaterElements(int[] nums) {
        if (nums.length == 0) return new int[0];
        int[] result = new int[nums.length];
        boolean[] visited = new boolean[nums.length];
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; ; i = (i + 1) % nums.length) {
            if (!queue.isEmpty() && i == (queue.peekFirst() + 1) % nums.length && visited[i]) break;
            while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) result[queue.pollLast()] = nums[i];
            if (!visited[i]) queue.addLast(i);
            visited[i] = true;
        }
        while (!queue.isEmpty()) result[queue.poll()] = -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};
        NextGreaterElementIIOPT3 tester = new NextGreaterElementIIOPT3();
        for (int i : tester.nextGreaterElements(input3)) System.out.println(i);
    }
}

这个算法的核心是很类似 Stack 算法的, 不过速度快很多, 34ms; 而且相比于pure array的算法, 也简洁很多;我把几个括号删了之后, 居然还慢了, 37ms;

或许可以说list 比 Stack 会快一些? 虽然都可以完成类似的功能;

当然这个算法本身还是有一定的自己的特别之处的, 比如这里的 for 循环其实没有termination condition, 这个是一个不常见的思路. 当然, 相应的, 里面的 break 语句也就不是很好理解. 以1,2,1为例, 最后 break 之后, queue 里面剩下的肯定全都是最大值(的 index, 一定要注意体型自己 queue 啊, Stack 啊这些里面到底存的是什么. 这里存的就是 index),所以只要至少走了一圈(最大值之后一个数is already visited), 就可以 break 了. 然后出去把最大值的几个相应处理一下就行了.

这个算法的作者好像是个妹子, 算法本身还算挺巧妙的. 虽然不是最优中的最优, 不过比简单的 Stack 已经提升很多;

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