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]从sync.waitgroup看内存对齐

Golang flag是什么

Golang可以写web吗？

手撸Golang 基本数据结构与算法快速排序

Go语言指向指针的指针

mac怎么搭建Go语言开发环境

Go 中使用 json 时，如何区分空字段和未设置字段

手撸Golang 行为型设计模式命令模式