LeetCode 556. 下一个更大元素 III

Categories:

Tags:

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

题目描述

✅ 556. 下一个更大元素 III

思路分析

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

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

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

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

交换数字 i 和 j。

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

参考代码

func nextGreaterElement(num int) int {
	chars := []byte(strconv.Itoa(num))
	n := len(chars)
	i := n - 2

	for i >= 0 && chars[i] >= chars[i+1] {
		i--
	}

	if i < 0 {
		return -1
	}

	j := n - 1
	for j >= 0 && chars[j] <= chars[i] {
		j--
	}

	chars[i], chars[j] = chars[j], chars[i]
	reverse(chars, i+1, n-1)

	res, _ := strconv.Atoi(string(chars))
	if res > math.MaxInt32 {
		return -1
	}
	return res
}

func reverse(nums []byte, i, j int) {
	for i < j {
		nums[i], nums[j] = nums[j], nums[i]
		i++
		j--
	}
}

func nextGreaterElement(n int) int {
	nums := []byte(strconv.Itoa(n))
	length := len(nums)

	// 1. 找到第一个不满足递增的元素
	i := length - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}
	if i < 0 {
		return -1
	}

	if i >= 0 {
		// 2. 找到第一个比 nums[i] 大的元素
		j := length - 1
		for nums[j] <= nums[i] {
			j--
		}
		// 3. 交换
		nums[i], nums[j] = nums[j], nums[i]
	}

	// 4. 反转 i + 1 到 length - 1 的部分
	reverse(nums, i+1, length-1)

	// 5. 转换回整数并检查范围
	res, _ := strconv.Atoi(string(nums))
	if res > math.MaxInt32 {
		return -1
	}
	return res
}

func reverse(nums []byte, start int, end int) {
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}
}

时间复杂度：O(n)，其中 n 是数字位数。最多遍历两次。

空间复杂度：O(n)，用于存储数字数组（byte 类型）。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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