题目来源
503. 下一个更大元素 II - 力扣（LeetCode）
题目描述
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
提示
- 1 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
题目解析
本题是 LeetCode - 496 下一个更大元素 I-CSDN博客 升级。大家需要现看懂前面这题，才能继续看本题。
本题相较于 496题 的变化在于，nums 数组是首尾相连的，即 nums[nums.length - 1] 下一个更大元素，可以继续从 nums[0] 开始找。
因此，本题最简单的思路就是，将 496题 的遍历逻辑重复两次。两轮共用一个栈。
- 第一次遍历结束时，栈中可能会剩余一些未找到下一个更大值的元素。
- 第二次遍历的目的是：找到第一次结束后，栈中剩余元素的下一个更大值的元素。（PS：因此第二轮遍历时，就可以去除压栈逻辑，仅保留弹栈和比较大小的逻辑）。
C算法源码
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {int* ans = (int*)malloc(sizeof(int) * numsSize);for (int i = 0; i < numsSize; i++) {ans[i] = -1;}// stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素// stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质int stack[10001];int stack_size = 0;// 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组for (int i = 0; i < numsSize * 2; i++) {// 避免 i 索引越界int j = i % numsSize;// 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质while (stack_size > 0 && nums[j] > nums[stack[stack_size - 1]]) {// 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）ans[stack[--stack_size]] = nums[j];}// 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质if(i < numsSize) { // 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。stack[stack_size++] = j;}}*returnSize = numsSize;return ans;
}C++算法源码
class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> ans(nums.size(), -1);// stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素// stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质deque<int> stack;// 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组for (int i = 0; i < nums.size() * 2; i++) {// 避免 i 索引越界int j = i % nums.size();// 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质while (!stack.empty() && nums[j] > nums[stack.back()]) {// 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）ans[stack.back()] = nums[j];stack.pop_back();}// 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质if(i < nums.size()) { // 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。stack.push_back(j);}}return ans;}
};JS算法源码
/*** @param {number[]} nums* @return {number[]}*/
var nextGreaterElements = function (nums) {const ans = new Array(nums.length).fill(-1);// stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素// stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质const stack = [];// 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组for (let i = 0; i < nums.length * 2; i++) {// 避免 i 索引越界const j = i % nums.length;// 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质while (stack.length > 0 && nums[j] > nums[stack.at(-1)]) {// 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）ans[stack.pop()] = nums[j];}// 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质if(i < nums.length) { // 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。stack.push(j);}}return ans;
};Java算法源码
class Solution {public int[] nextGreaterElements(int[] nums) {int[] ans = new int[nums.length];Arrays.fill(ans, -1);// stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素// stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质ArrayDeque<Integer> stack = new ArrayDeque<>();// 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组for (int i = 0; i < nums.length * 2; i++) {// 避免 i 索引越界int j = i % nums.length;// 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质while (!stack.isEmpty() && nums[j] > nums[stack.peek()]) {// 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）ans[stack.pop()] = nums[j];}// 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质if(i < nums.length) { // 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。stack.push(j);}}return ans;}
}Python算法源码
class Solution(object):def nextGreaterElements(self, nums):""":type nums: List[int]:rtype: List[int]"""ans = [-1] * len(nums)# stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素# stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质stack = []# 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组for i in range(len(nums) * 2):# 避免 i 索引越界j = i % len(nums)# 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质while stack and nums[j] > nums[stack[-1]]:# 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）ans[stack.pop()] = nums[j]# 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质if i < len(nums): # 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。stack.append(j)return ans
