LeetCode 556. 下一个更大元素 III

Categories:

题目描述
思路分析
1. 解法一：下一个排列（推荐）
相似题目

题目描述

✅ 556. 下一个更大元素 III

思路分析

解法一：下一个排列（推荐）

核心思路：

本题与 LeetCode 31「下一个排列」逻辑完全相同，只是输入为整数而非数组。

将整数的各位数字提取为字节数组，在数组上执行「下一个排列」算法：

从右向左找第一个下降点 i（即 digits[i] < digits[i+1]）；

若找不到，说明当前已是最大排列，返回 -1；

从右向左找第一个严格大于 digits[i] 的位置 j，交换 digits[i] 与 digits[j]；

将 i+1 到末尾的部分翻转为升序，得到下一个排列。

最后将字节数组转回整数，若超出 32 位有符号整数范围（> Integer.MAX_VALUE），返回 -1。

复杂度分析：

时间复杂度：O(n)，其中 n 表示整数的位数，最多遍历数组常数次。

空间复杂度：O(n)，其中 n 表示整数的位数，用于存储各位数字的字节数组。

class Solution {
    public int nextGreaterElement(int n) {
        // 将整数转为字符数组，方便对各位数字进行操作
        char[] digits = Integer.toString(n).toCharArray();
        int len = digits.length;

        // 从右向左找第一个下降点 i（digits[i] < digits[i+1]）
        int i = len - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }

        // 若整个数组单调不递增，当前已是最大排列，返回 -1
        if (i < 0) {
            return -1;
        }

        // 从右向左找第一个严格大于 digits[i] 的位置 j
        int j = len - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }

        // 交换 digits[i] 与 digits[j]
        char tmp = digits[i];
        digits[i] = digits[j];
        digits[j] = tmp;

        // 翻转 i+1 到末尾，使后半部分变为最小排列
        reverse(digits, i + 1, len - 1);

        // 转换为 long 检查是否超出 int 范围
        long res = Long.parseLong(new String(digits));
        return res > Integer.MAX_VALUE ? -1 : (int) res;
    }

    private void reverse(char[] digits, int left, int right) {
        while (left < right) {
            char tmp = digits[left];
            digits[left] = digits[right];
            digits[right] = tmp;
            left++;
            right--;
        }
    }
}

func nextGreaterElement(n int) int {
	// 将整数转为字节数组，方便对各位数字进行操作
	digits := []byte(strconv.Itoa(n))
	length := len(digits)

	// 从右向左找第一个下降点 i（digits[i] < digits[i+1]）
	i := length - 2
	for i >= 0 && digits[i] >= digits[i+1] {
		i--
	}

	// 若整个数组单调不递增，当前已是最大排列，返回 -1
	if i < 0 {
		return -1
	}

	// 从右向左找第一个严格大于 digits[i] 的位置 j
	j := length - 1
	for digits[j] <= digits[i] {
		j--
	}

	// 交换 digits[i] 与 digits[j]
	digits[i], digits[j] = digits[j], digits[i]

	// 翻转 i+1 到末尾，使后半部分变为最小排列
	reverseBytes(digits, i+1, length-1)

	// 转换为整数并检查是否超出 int32 范围
	res, _ := strconv.Atoi(string(digits))
	if res > math.MaxInt32 {
		return -1
	}
	return res
}

func reverseBytes(digits []byte, left, right int) {
	for left < right {
		digits[left], digits[right] = digits[right], digits[left]
		left++
		right--
	}
}

相似题目

题目	难度	考察点
31. 下一个排列	中等	双指针 / 从右到左找降序
496. 下一个更大元素 I	简单	单调栈 / 哈希表
503. 下一个更大元素 II	中等	单调栈 / 循环数组
670. 最大交换	中等	贪心 / 数位重排
738. 单调递增的数字	中等	贪心 / 从右往前处理
60. 排列序列	困难	数学 / 康托展开

本文作者: HGNULB

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