leetcode503 下一个更大元素 II golang

503. 下一个更大元素 II

解题思路

模拟解法，利用下标优化。
设 A[i]表示数组中下一个大于nums[i]的下标，如果不存在则标记为i。
我们从后向前遍历数组，利用动态规划，所有大于当前下标 current_i 的都已经计算过了。

1. 对于大于 current_i 的下标 j , 如果 nums[j] 大于nums[current_i],则A[i]=j
2. 如果小于，则令 j = A[j],去下一个大于nums[j]的下标。这里有2个case需要处理
   1. 如果 j > i && A[j] == j 则证明不存在数大于A[j],而A[i]>=A[j],更不存在，所以A[i]=j
   2. 如果 j <i证明还没有计算，则j++

代码

func nextGreaterElements(nums []int) []int {
    A := make([]int, len(nums))
    n := len(A)
    for i := n - 1; i >= 0; i-- {
        A[i] = i
        for j := i + 1; j != i; {
            j %= n
            if j == i {
                break
            }
            if nums[j] > nums[i] {
                A[i] = j
                break
            }
            if j > i {
                if A[j] == j {
                    break
                } else {
                    j = A[j]
                }
            } else {
                j++
            }
        }
    }
    for i:=range A{
        if A[i]==i{
            A[i]=-1
        }else{
            A[i]=nums[A[i]]
        }
    }
    return A
}

有疑问加站长微信联系（非本文作者）