灵神常见算法

503. 下一个更大元素 II

• 使用单调栈

func nextGreaterElements(nums []int) []int {
	n := len(nums)
	var stack []int // 栈
	ans := make([]int, n)
	for i := range ans { // 初始化ans数组为-1
		ans[i] = -1
	}

	for i := 0; i < 2*n-1; i++ { // 循环数组，n次后，再遍历n-1次
		top := len(stack)                               // 栈顶
		for top > 0 && nums[stack[top-1]] < nums[i%n] { // nums[i]比栈顶更大，找到下一个更大，弹出栈顶
			ans[stack[top-1]] = nums[i%n] // 记录下一个更大元素
			stack = stack[:top-1]         // 弹出栈顶
			top = len(stack)              // 栈顶变化
		}
		stack = append(stack, i%n) // nums[i]比栈顶小，不是下一个更大元素，压入栈顶
	}
	return ans
}