LeetCode 556. 下一个更大元素 III

Categories:

题目描述
思路分析
参考代码

题目描述

🔥 556. 下一个更大元素 III

思路分析

要找出下一个更大的整数，可以按照以下步骤来解决这个问题：

从右到左遍历数字，找到第一个不符合升序顺序的数字，记为 i。

如果找不到这样的数字，表示当前整数已经是最大的，无法找到更大的整数，返回 -1。

否则，再次从右到左遍历数字，找到第一个大于 i 的数字，记为 j。

交换数字 i 和 j。

对数字 i 右侧的数字进行升序排序，以获得下一个更大的整数。

参考代码

func nextGreaterElement(n int) int {
	nums := []rune(strconv.Itoa(n))
	if len(nums) < 2 {
		return -1
	}

	i := len(nums) - 2

	// 找到第一个不符合升序顺序的数字
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}

	if i < 0 {
		return -1 // 整数已经是最大的，无法找到更大的整数
	}

	j := len(nums) - 1

	// 找到第一个大于 nums[i] 的数字
	for nums[j] <= nums[i] {
		j--
	}

	// 交换数字 i 和 j
	nums[i], nums[j] = nums[j], nums[i]

	// 对数字 i 右侧的数字进行升序排序
	left, right := i+1, len(nums)-1
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}

	res, err := strconv.Atoi(string(nums))
	if err != nil || res > math.MaxInt32 {
		return -1
	}

	return res
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/31938115