leetcode-503 下一个更大元素 II

题目描述:给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] cycle = new int[nums.length * 2];
System.arraycopy(nums, 0, cycle, 0, nums.length);
System.arraycopy(nums, 0, cycle, nums.length, nums.length);
int[] res = new int[cycle.length];
Stack<Integer> stack = new Stack<>();
for (int i = cycle.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() <= cycle[i]) {
stack.pop();
}
int nextMax = stack.isEmpty() ? -1 : stack.peek();
res[i] = nextMax;
stack.push(cycle[i]);
}
return Arrays.copyOf(res,nums.length);
}
}