leetcode503 下一个更大元素 II golang-木庄网络博客

本文摘自网络，作者，侵删。

503. 下一个更大元素 II

解题思路

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

对于大于 current_i 的下标 j , 如果 nums[j] 大于nums[current_i],则A[i]=j
如果小于，则令 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
}

本文来自：简书

感谢作者：lucasgao

查看原文：leetcode503 下一个更大元素 II golang

相关阅读 >>

Golang中自定义包

聊聊dapr的consistent hash

Golang 是什么

Go的切片（进阶版）

云边端架构easydss内Go语言如何生成归档文件？

Go语言从入门到实战,带你拿下Golang的高效编程法

最新字节跳动面试题与答案: 无序数组的中位数 (快排思想o(n) 时间复杂度)

Go语言学习9-结构体类型