Typical ways to solve circular array problems. Java solution.
The first typical way to solve circular array problems is to extend the original array to twice length, 2nd half has the same element as first half. Then everyt
The first typical way to solve circular array problems is to extend the original array to twice length, 2nd half has the same element as first half. Then everything become simple.\nNaive by simple solution, just look for the next greater element directly. Time complexity: O(n^2).\n```\npublic class Solution {\n    public int[] nextGreaterElements(int[] nums) {\n        int max = Integer.MIN_VALUE;\n        for (int num : nums) {\n            max = Math.max(max, num);\n        }\n        \n        int n = nums.length;\n        int[] result = new int[n];\n        int[] temp = new int[n * 2];\n        \n        for (int i = 0; i < n * 2; i++) {\n            temp[i] = nums[i % n];\n        }\n        \n        for (int i = 0; i < n; i++) {\n            result[i] = -1;\n            if (nums[i] == max) continue;\n            \n            for (int j = i + 1; j < n * 2; j++) {\n                if (temp[j] > nums[i]) {\n                    result[i] = temp[j];\n                    break;\n                }\n            }\n        }\n        \n        return result;\n    }\n}\n```\n\nThe second way is to use a ```stack``` to facilitate the look up. First we put all indexes into the stack, ```smaller``` index on the ```top```. Then we start from ```end``` of the array look for the first element (index) in the stack which is greater than the current one. That one is guaranteed to be the ```Next Greater Element```. Then put the current element (index) into the stack.\nTime complexity: O(n).\n```\npublic class Solution {\n    public int[] nextGreaterElements(int[] nums) {\n        int n = nums.length;\n        int[] result = new int[n];\n        \n        Stack<Integer> stack = new Stack<>();\n        for (int i = n - 1; i >= 0; i--) {\n            stack.push(i);\n        }\n        \n        for (int i = n - 1; i >= 0; i--) {\n            result[i] = -1;\n            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {\n                stack.pop();\n            }\n            if (!stack.isEmpty()){\n                result[i] = nums[stack.peek()];\n            }\n            stack.add(i);\n        }\n        \n        return result;\n    }\n}\n```
[]