503. Next Greater Element II
https://leetcode.com/problems/next-greater-element-ii/
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.
--
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int[] nextGreaterElements(int[] nums) { | |
| Stack<Integer> stack = new Stack<Integer>(); | |
| int[] ans = new int[nums.length]; | |
| Arrays.fill(ans, -1); | |
| for (int i = 0; i < nums.length; i++) { | |
| while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { | |
| ans[stack.pop()] = nums[i]; | |
| } | |
| stack.push(i); | |
| } | |
| // Wrap around => find greater elements for elements on the end | |
| // Don't push to stack anymore | |
| for (int i = 0; i < nums.length; i++) { | |
| while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { | |
| ans[stack.pop()] = nums[i]; | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
