友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
503. 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; </br>The number 2 can't find next greater number; </br>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.
思路分析
循环数组+单调栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 参考 496 题，自己写出来的
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-05 23:08:39
*/
public int[] nextGreaterElements(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int[] result = new int[nums.length];
Deque<Integer> stack = new LinkedList<>();
// 只需要将数组“拼接”，遍历两遍数组，就可以解决所有元素后继更大元素的问题
// 从后向前遍历，再加上单调递增栈，就是时间复杂度为 O(n) 的解决方案
for (int i = 2 * nums.length - 1; i >= 0; i--) {
// 取余即可获取当前需要处理的元素
int index = i % nums.length;
// 在单调栈不为空的情况下，将栈中小于等于当前元素的值都弹出
while (!stack.isEmpty() && stack.peek() <= nums[index]) {
stack.pop();
}
// 剩下元素既是比当前元素大的后继元素。为空则是没有更大元素
// 这里还有一个隐含变量：
// 由于栈是从后向前添加，则栈顶元素距离当前元素更近。
// 如果栈不为空，则栈顶元素就是符合条件的元素。
result[index] = stack.isEmpty() ? -1 : stack.peek();
stack.push(nums[index]);
}
return result;
}