题目地址
https://leetcode.com/problems/next-greater-element-ii/
题目描述
503. Next Greater Element II
Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.
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, return -1 for this number.
Example 1:
Input: nums = [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.
Example 2:
Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]
思路
- 单调栈. 用单调栈维护当前位置还没找到最大值的元素index列表, 从栈底到栈顶的元素单调递减.
关键点
- 与I的区别是环形, 因此可以拼接一遍数组来求解.
代码
- 语言支持:Java
class Solution {
public int[] nextGreaterElements(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
for (int i = 0; i < 2 * n; i++) {
while (!stack.isEmpty() && nums[stack.peek() % n] < nums[i % n]) {
int index = stack.pop();
res[index % n] = nums[i % n];
}
stack.push(i);
}
return res;
}
}
网友评论