esc to dismiss

503. 下一个更大元素 II

题目

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

示例 1:

输入: [1,2,1]

输出: [2,-1,2]

解释: 第一个 1 的下一个更大的数是 2;

数字 2 找不到下一个更大的数;

第二个 1 的下一个最大的数需要循环搜索,结果也是 2

解体思路

这也是一个典型的 单调栈 算法题。

需要注意的是:由于题中要求循环搜索,因此,一次轮循增加单调栈还不够,得两次。(注意,第二次不用往单调栈中增加元素。)

func nextGreaterElements(nums []int) []int {
    var mono []int
    size := len(nums)
    g := make([]int, size, size)

    for i, v := range nums {
        for len(mono) > 0 && nums[mono[len(mono)-1]] < v {
            g[mono[len(mono)-1]] = v
            mono = mono[:len(mono)-1]
        }
        mono = append(mono, i)
    }

    for _, v := range nums {
        if len(mono) == 0 {
            return g
        }

        for nums[mono[len(mono)-1]] < v {
            g[mono[len(mono)-1]] = v
            mono = mono[:len(mono)-1]
        }
    }

    for _, v := range mono {
        g[v] = -1
    }

    return g
}

经验教训

...

x