问题描述

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.

计算环形数组中的下一个Next Greater元素，若不存在，则返回-1。

举个例子：

Input:  [1,2,1]
Output: [2,-1,2]

基础题：

[496] Next Greater Element I{:target=”_blank”}

解法1

Thanks @lee215{:target=”_blank”}

这道题的难点在于如何找到最后一个元素的Next Greater。

一种解决方案就是，遍历两次数组。

来看下实现：

class Solution {
    public int[] nextGreaterElements(int[] nums) {

        int n = nums.length;
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int[] ans = new int[n];

        for (int i = (n << 1) - 1; i >= 0; i--){
            int cur = nums[i % n];
            while (!stack.isEmpty() && cur >= stack.peek()){
                stack.pop();
            }
            ans[i % n] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(cur);
        }
        return ans;
    }
}

Enjoy it !