503. 下一个更大元素 II

🟠   🔖  栈 数组 单调栈  🔗 力扣 LeetCode

题目

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]

Constraints:

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9

题目大意

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

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

解题思路

这题是 第 496 题 的加强版，在第 496 题的基础上增加了循环数组的条件。

可以依旧按照第 496 题的做法，用单调栈，栈中记录单调递增的下标。

只不过由于是循环数组，所以需要在原数组的基础上，将数组前 n−1 个元素拼接在原数组的后面，进行遍历，实际代码中，不需要真正拼接数组，只需对下标取模即可。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function (nums) {
	let stack = [];
	let len = nums.length;
	let res = new Array(len).fill(-1);
	for (let i = 0; i < 2 * len - 1; i++) {
		let idx = i % len;
		while (stack.length && nums[idx] > nums[stack[stack.length - 1]]) {
			res[stack.pop()] = nums[idx];
		}
		stack.push(idx);
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
496	下一个更大元素 I	[✓]	栈 数组 哈希表 1+
556	下一个更大元素 III		数学 双指针 字符串