Next Greater Element II

Leave a comment

June 21, 2017 by oneOokay

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.


有两种方法:1.把array延长为原来的两倍;2.用stack(非常妙)

stack的方法:
1. 把array的 INDEX 按从大到小的顺序push入栈(所以栈的pop顺序就把index从小到大pop出来.
2. 从array的最后一个数字开始遍历:
– 如果nums在栈顶INDEX的值小于当前array index = i的值的话,pop
– 一直pop到栈顶INDEX的值大于当前array index = i. 把nums[stack.peek()]的值写到res[i]里.
– 这样pop的一个过程就是从i向后circle loop array的一个过程.
– 当栈为空,说明当前值为最大值之一,所以res[i]为-1.
– 在遍历下一个array数字之前,把当前的i加入到stack里面,来维持一个”从i向后circle loop”的index
– 有一些被pop掉的元素会不会对结果有影响呢?不会
– 比如说当前i = 4, i = 0和1 pop掉了(说明i=2的值是大于i=4的),i=4加入到了stack里面.判断i = 3的时候:
– 如果i = 3的值等于i=4的值,那么i=4会被pop出去,i=3会同样的取到i=2的值
– 如果i = 3的值小于i=4的值,那么i = 4就是比i=3第一个大的元素,值取i=3的值
– 如果i = 3的值大于i=4的值,i=4会被pop出去,那么其实之前被pop出去的i = 0,1都不需要考虑,因为他们既然比i=4小,那就也都会被pop出去,存不存在于stack里面也就无所谓了.只需要与接下来没有被i=4pop出去的i=2及其之后的值进行比较即可.
– 注意这里不能在原数组上进行操作.要新建一个res数组.
    public int[] nextGreaterElements(int[] nums) {
        Stack s = new Stack<>();
        int len = nums.length;
        int[] res = new int[len];
        for (int i = len - 1; i >= 0; i --){
            s.push(i);
        }
        
        for (int i = len - 1; i >= 0; i --){
            while (!s.isEmpty() && nums[s.peek()] <= nums[i]){
                s.pop();
            }
            if (!s.isEmpty()){
                res[i] = nums[s.peek()];
            }else {
                res[i] = -1;
            }
            s.push(i);
        }
        return res;
    }

新建一个新的tmp array,长度为原来的2倍.后半段就是完全复制前半段的值.

其中tmp[i] = nums[i % len]

loop的时候的范围是 i 到 i + len

public int[] nextGreaterElements(int[] nums) {
        int max = Integer.MIN_VALUE;
        int len = nums.length;
        int[] tmp = new int[len * 2];
        for (int i = 0; i < 2 * len; i ++){
            tmp[i] = nums[i % len];
            max = Math.max(max, tmp[i]);
        }
        
        for (int i = 0; i < len; i ++){
            if (nums[i] == max){
                nums[i] = -1;
                continue;
            }
            for (int j = i + 1; j < len + i; j ++){
                 if (tmp[j] > nums[i]){
                    nums[i] = tmp[j];
                    break;
                }
            }
        }
        return nums;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: