package question;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question503 {
 public int[] nextGreaterElements(int[] nums) {
 int n = nums.length;
 Stack<Integer> stack = new Stack<>();
 int[] res = new int[n];
 Arrays.fill(res, -1);
 for (int i = 0; i < 2 * n - 1; i++) {
 while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
 res[stack.pop()] = nums[i % n];
 }
 stack.push(i % n);
 }
 return res;
 }

 public int[] nextGreaterElements2(int[] nums) {
 int n = nums.length;
 int[] res = new int[n];
 for (int i = 0; i < n; i++) {
 int j = i + 1;
 for (; j < i + n; j++) {
 if (nums[j % n] > nums[i]) {
 res[i] = nums[j % n];
 break;
 }
 }
 if (j == i + n) res[i] = -1;
 }
 return res;
 }
}