2454. 下一个更大元素 IV

2454. 下一个更大元素 IV

• 难度: hard
• 原始链接: https://leetcode.cn/problems/next-greater-element-iv
• 标签: 单调栈

解法一: 单调栈

go

func secondGreaterElement(nums []int) []int {
    length := len(nums)
    ans := make([]int, length)
    for i := 0; i < length; i++ {
        ans[i] = -1
    }
    list1 := []int{}
    list2 := []int{}
    for i, num := range nums {
        for len(list2) > 0 && nums[list2[len(list2) - 1]] < num {
            ans[list2[len(list2) - 1]] = num
            list2 = list2[:len(list2) - 1]
        }
        pos := len(list1) - 1
        for pos >= 0 && nums[list1[pos]] < num {
            pos--
        }
        list2 = append(list2, list1[pos + 1:]...)
        list1 = append(list1[:pos + 1], i)
    }
    return ans
}

其他 “下一个更大元素”

496. 下一个更大元素 I

go

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    stack := []int{}
    length2 := len(nums2)
    moreLargeArr := make(map[int]int, length2)
    for i := length2 - 1; i >= 0; i-- {
        for len(stack) > 0 && stack[len(stack) - 1] < nums2[i] {
            stack = stack[:len(stack) - 1]
        }
        if len(stack) == 0 {
            moreLargeArr[nums2[i]] = -1
        } else {
            moreLargeArr[nums2[i]] = stack[len(stack) - 1]
        }
        stack = append(stack, nums2[i])
    }
    length1 := len(nums1)
    ans := make([]int, length1)
    for i, num := range nums1 {
        ans[i] = moreLargeArr[num]
    }
    return ans
}

503. 下一个更大元素 II

go

func nextGreaterElements(nums []int) []int {
    stack := []int{}
    n := len(nums)
    doubleN := n << 1
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        ans[i] = -1
    }
    for i := 0; i < doubleN; i++ {
        for len(stack) > 0 && nums[stack[len(stack) - 1]] < nums[i % n] {
            ans[stack[len(stack) - 1]] = nums[i % n]
            stack = stack[:len(stack) - 1]
        }
        stack = append(stack, i % n)
    }
    return ans
}

556. 下一个更大元素 III

go

func nextGreaterElement(n int) int {
    nums := toArr(n)
    length := len(nums)
    for i := len(nums) - 2; i >= 0; i-- {
        if nums[i] < nums[i + 1] {
            sort.Ints(nums[i + 1:])
            for j := i + 1; j < length; j++ {
                if nums[i] < nums[j] {
                    nums[i], nums[j] = nums[j], nums[i]
                    break
                }
            }
            maxMinNum := toNum(nums)
            if maxMinNum <= math.MaxInt32 {
                return maxMinNum
            }
            break
        }
    }
    return -1
}

func toArr(n int) []int {
    arr := []int{}
    for n != 0 {
        arr = append(arr, n % 10)
        n /= 10
    }
    for i, j := 0, len(arr) - 1; i < j; i, j = i + 1, j - 1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
    return arr
}

func toNum(nums []int) int {
    num := 0
    for i := 0; i < len(nums); i++ {
        num = num * 10 + nums[i]
    }
    return num
}