题目链接：503

思路

本题使用单调栈解决。

我对单调栈的理解是：能够解决 “相邻的”、“单调的” 元素间的关系。这里的 “相邻” 指的并不是在原数组中相邻，而是指 “寻找离的最近的符合条件的元素”。本题需要寻找离得最近的更大的元素。“更大元素” 符合 “单调性”，“离得最近” 符合 “相邻性”，因此适合使用单调栈完成。

还有一个技巧点在于对循环队列的处理。在思考循环队列问题时，可以考虑将多个循环队列首尾拼接起来形成一个普通队列，遍历这个普通队列 和 循环遍历循环队列 的结果是一样的。基于普通队列思考问题会更加直观，但在代码实现时并不用真的拼接一个普通队列出来，只需要对下标取模就行了。

// use monotone stack
func nextGreaterElements(nums []int) []int {
    n := len(nums)
    // init ans
    ans := make([]int, len(nums))
    for i := range ans {
        ans[i] = -1
    }
    // init monotone stack
    s := make([]int, 1)
    s[0] = 0

    // imagine to traverse a concat list
    for i := 1; i < 2*n - 1; i++ {
        // see the top element of stack
        for len(s) > 0 && nums[s[len(s) - 1]] < nums[i % n] {
            ans[s[len(s) - 1]] = nums[i % n]
            // pop
            s = s[:len(s) - 1]
        }
        // push
        s = append(s, i % n)
    }
    return ans
}