目标
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]说明:
- 1 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
思路
暴力解法需要针对每一个元素向后搜索，时间复杂度为O(n^2)。这里面有一些重复的操作，例如，数组 [5,4,3,2,1,6] 找下一个更大的元素，从 5 向后搜索 与从 4 向后搜索有重复的部分 3 2 1。单调栈的核是这样处理的，先将第一个元素下标压入栈中，指针移到下一个元素，如果栈顶对应元素大于等于当前元素则将当前元素下标也压入栈中，否则弹栈，记录 res[stack.pop()] = 当前元素，直到栈顶元素大于等于当前元素。
针对这个题目，栈中保存的下标对应的元素值从栈底到栈顶是单调递减的，如果遇到第一个更大元素就弹栈了，因此称为单调栈。
这样做的好处是避免了重复的查找，它将重复搜索的部分使用栈保存了起来，这样就变成了从后向前搜索。如果栈顶元素遇到了第一个更大的元素，那么它也是前面同样小于该值的第一个更大元素，从而避免了重复查找。
这里对循环数组的处理是将原数组拼接到后面，下标进行取模运算。
代码
/**
* @date 2024-06-24 0:18
*/
public class NextGreaterElements503 {
public int[] nextGreaterElements_v4(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
int[] stack = new int[n];
int top = -1;
for (int i = 0; i < 2 * n - 1; i++) {
int index = i % n;
while (top > -1 && nums[stack[top]] < nums[index]) {
res[stack[top--]] = nums[index];
}
if (i < n) {
stack[++top] = index;
}
}
return res;
}
}
性能
