503. 下一个更大元素 II
题目描述
输入整数数组 nums，把它看成首尾相连的环：最后一个元素之后紧接着是 nums[0]。
对每个元素，从它的下一个位置开始沿环向后查找，遇到的第一个比它大的数就是它的下一个更大元素；绕回到自身仍找不到时记为 -1。
返回与 nums 等长的数组，第 i 项是 nums[i] 的下一个更大元素。
示例 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]
解释：4 是最大值记 -1，末尾的 3 绕回后在 4 处找到更大值。
数据范围
1 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9
解题思路
先想非循环版：用单调栈存“还没找到答案”的下标，对应值从底到顶非递增；新数比栈顶大时就是栈顶的答案。循环的意思是末尾的数还可以看开头，等价于把数组复制一份接在后面。所以下标 k 从 0 走到 2n-1，用 i = k % n 取值；第二轮只用来给栈里剩下的元素找答案，不再入栈。
为什么正确
栈中下标对应的值从底到顶非递增，它们都还没遇到比自己大的数。
复杂度分析
时间 O(n)（每个下标最多入栈、出栈各一次，循环 2n 步），空间 O(n)。
易错点
栈里要存下标而不是值，因为有重复值且答案要写到对应位置。第二轮不要再入栈，否则会把答案写两次（虽然结果相同）。比较用严格小于，相等不算更大。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [-1] * n
stack = []
for k in range(2 * n):
i = k % n
while stack and nums[stack[-1]] < nums[i]:
res[stack.pop()] = nums[i]
if k < n:
stack.append(i)
return resclass Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int k = 0; k < 2 * n; k++) {
int i = k % n;
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
res[stack.pop()] = nums[i];
}
if (k < n) {
stack.push(i);
}
}
return res;
}
}class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
vector<int> stack;
for (int k = 0; k < 2 * n; k++) {
int i = k % n;
while (!stack.empty() && nums[stack.back()] < nums[i]) {
res[stack.back()] = nums[i];
stack.pop_back();
}
if (k < n) {
stack.push_back(i);
}
}
return res;
}
};func nextGreaterElements(nums []int) []int {
n := len(nums)
res := make([]int, n)
for i := range res {
res[i] = -1
}
stack := []int{}
for k := 0; k < 2*n; k++ {
i := k % n
for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
res[stack[len(stack)-1]] = nums[i]
stack = stack[:len(stack)-1]
}
if k < n {
stack = append(stack, i)
}
}
return res
}var nextGreaterElements = function(nums) {
const n = nums.length;
const res = new Array(n).fill(-1);
const stack = [];
for (let k = 0; k < 2 * n; k++) {
const i = k % n;
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
res[stack.pop()] = nums[i];
}
if (k < n) {
stack.push(i);
}
}
return res;
};function nextGreaterElements(nums: number[]): number[] {
const n = nums.length;
const res: number[] = new Array(n).fill(-1);
const stack: number[] = [];
for (let k = 0; k < 2 * n; k++) {
const i = k % n;
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
res[stack.pop()!] = nums[i];
}
if (k < n) {
stack.push(i);
}
}
return res;
}