題目鏈接：503

思路

本題使用單調(diào)棧解決。

我對(duì)單調(diào)棧的理解是：能夠解決 “相鄰的”、“單調(diào)的” 元素間的關(guān)系。這里的 “相鄰” 指的并不是在原數(shù)組中相鄰，而是指 “尋找離的最近的符合條件的元素”。本題需要尋找離得最近的更大的元素?！案笤亍?符合 “單調(diào)性”，“離得最近” 符合 “相鄰性”，因此適合使用單調(diào)棧完成。

還有一個(gè)技巧點(diǎn)在于對(duì)循環(huán)隊(duì)列的處理。在思考循環(huán)隊(duì)列問(wèn)題時(shí)，可以考慮將多個(gè)循環(huán)隊(duì)列首尾拼接起來(lái)形成一個(gè)普通隊(duì)列，遍歷這個(gè)普通隊(duì)列 和 循環(huán)遍歷循環(huán)隊(duì)列 的結(jié)果是一樣的?；谄胀?duì)列思考問(wèn)題會(huì)更加直觀，但在代碼實(shí)現(xiàn)時(shí)并不用真的拼接一個(gè)普通隊(duì)列出來(lái)，只需要對(duì)下標(biāo)取模就行了。

// 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
}