JS Leetcode 503. 下一个更大元素 II 题解分析，依旧单调栈做法解决此题

壹 ❀ 引

我在JS Leetcode 496. 下一个更大元素 I 更清晰的图解单调栈做法一文中，介绍了单调栈做法解决下一个更大元素的问题，比较巧的是这道题还有升级版，题目来自Leetcode503. 下一个更大元素 II，描述如下：

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,2,1]

输出: [2,-1,2]

解释: 第一个 1 的下一个更大的数是 2；

数字 2 找不到下一个更大的数；

第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

这是第一道中等难度的题，但如果我们已知单调栈的玩法，你会发现此题难度就急剧下降了。

[1,2,1]

由于单调栈的具体做法在上题中已经介绍的很清楚了，所以这里不再复述，若不清楚推荐阅读上题的题解。所以对于此题，我们需要考虑的其实是解决循环的问题，较为直观的做法自然是将数组长度乘以2，这样就能保证数组最后的一个元素都能进行一次完整的查找。

[1,2,1]

比如上面例子数组的长度是3，取余就有如下现象：

0 % 3//0

1 % 3//1

2 % 3//2

3 % 3//0

4 % 3//1

5 % 3//2

…

i % length

/**



@param {number[]} nums

@return {number[]}

*/

var nextGreaterElements = function (nums) {

let stack = [];

let len = nums.length;

let ans = [];

// 还是一样的倒序循环，这里只是把长度加倍了而已，回想下站队后往后看第一个比自己高的人。

for (let i = len * 2 - 1; i >= 0; i–) {

    // 只要栈不为空，且当前的元素要高于或者等于栈顶的元素，那前面的人都会第一个看到当前遍历到的人，所以栈里的人没保存的必要了

    while (stack.length && nums[i % len] >= stack[stack.length - 1]) {

        stack.pop();

    };

    // 跟上道题没差别，只是i变成了i%len

    ans[i % len] = stack.length ? stack[stack.length - 1] : -1;

    stack.push(nums[i % len])

};

return ans;

};

[1,2,1,1,2,1][1,2,1]