503. 下一个更大元素II

题目描述：

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

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

测试用例：

示例 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]

限制及提示：

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

---

解题分析及思路：

本题可以采取单调栈 🔗进行解答。

方法一：暴力

本题使用暴力，同样可以解答。

遍历整个数组，为每一个元素往后找到比他大的元素，放入结果集中，若遍历一圈还未找到，则将-1保存到结果中

func nextGreaterElements(nums []int) []int {
	ans := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		index := (i + 1) % len(nums)
		for nums[index] <= nums[i] && index != i {
			index = (index + 1) % len(nums)
		}
		if index == i {
			ans[i] = -1
		} else {
			ans[i] = nums[index]
		}
	}
	return ans
}

复杂度：

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

执行结果：

• 执行用时：320 ms, 在所有 Go 提交中击败了5.01%的用户
• 内存消耗：6.3 MB, 在所有 Go 提交中击败了100.00%的用户

方法二：单调栈

使用单调栈保存元素下标。

每当遍历一个新的数组时，查看栈顶元素对应nums中的数值的是否小于当前元素值

• 若小于，将栈顶元素所对应的下标stack[len(stack)-1]弹出，并且更新结果集ans[stack[len(stack)-1]]的值
• 否则，将当前元素压入栈中。

为了更新全部的结果，需要遍历两次数组，因为考虑到一些额外的情况，例如[1,2,1]，如果只遍历一次，那么只有第一个元素更新了相应的结果。而此时，栈中有2,1两个元素。其中1所对应的结果并不知道。

func nextGreaterElements(nums []int) []int {
	l := len(nums)
	stack := make([]int, 0)
	ans := make([]int, l)
	for i := range ans {
		ans[i] = -1
	}
	for i := 0; i < 2*l; i++ {
		for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i%l] {
			ans[stack[len(stack)-1]] = nums[i%l]
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i%l)
	}
	return ans
}

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

执行结果：

• 执行用时：20 ms, 在所有 Go 提交中击败了93.87%的用户
• 内存消耗：6.5 MB, 在所有 Go 提交中击败了92.20%的用户