LeetCode 556. 下一个更大元素 III

2025-03-03 HGNULB 约 5 分钟

文章信息 8 个分类 4 个标签

分类

题目描述

✅ 556. 下一个更大元素 III

题意分析

给定一个正整数 n，要求在「用 n 的这些数字重新排列得到的所有整数」中，找出严格大于 n 的最小的那一个。注意重排必须用光全部数位且不能增删，因此候选集合是完全确定的，问题实质是在这个集合里找 n 的后继。

有两处限定必须同时满足，缺一个就会答错。第一，不存在比 n 更大的重排时返回 -1，这对应数位已经是从大到小完全降序的情况。第二，即便重排出了更大的数，如果它超出了 32 位有符号整数的表示范围，即大于 $2^{31} - 1$，同样必须返回 -1——题目的输入 n 本身在 int 范围内，但重排后的结果完全可能越界，比如把一个前导小数字换到高位就会让数值暴涨。

其它需要留意的点：n 是正整数所以不必考虑符号位和前导零；重排结果的位数与 n 完全相同，不会因为进位而变长；只有一位数时不存在任何其它排列，答案必然是 -1。返回值是数值而非字符串，所以最后一步的类型转换要与范围检查放在一起考虑。

解法：下一排列

核心思路

题目要求用相同数位组成刚好比 n 大的最小整数，本质是求数位序列的下一个字典序排列，而不是枚举所有排列。

从右向左找到第一个满足 digits[i] < digits[i+1] 的位置 i。此时 i 右侧是最长的非递增后缀，它已经是这些数位能组成的最大排列；若连 i 都找不到，整个数列非递增，不存在更大排列。

为了让增量最小，应在后缀中选择大于 digits[i] 的最小数位与它交换。由于后缀非递增，从右向左遇到的第一个更大数位正是该候选。交换后，更高位保持不变，i 位只增加了最小可能值。

最后把后缀反转成非递减顺序，使低位部分取到最小值。这样同时满足「大于原数」和「所有更大排列中最小」。结果可能超过 32 位有符号整数上限，必须先用 64 位整数解析再判断。

解题步骤

将 n 转成十进制字符数组。

从倒数第二位向左找 digits[i] < digits[i+1]；找不到则返回 -1。

从末尾向左找第一个 digits[j] > digits[i]，交换 i 和 j。

反转区间 [i+1, end]，把非递增后缀变为最小的非递减排列。

使用 64 位整数解析结果；若大于 $2^{31}-1$，返回 -1。

例如 n = 12443322：最长非递增后缀是 443322，枢轴为前面的 2；从右找到最小的更大数位 3 交换，再反转后缀，得到 13222344。

代码实现

class Solution {
    public int nextGreaterElement(int n) {
        char[] digits = String.valueOf(n).toCharArray();

        int pivot = digits.length - 2;
        while (pivot >= 0 && digits[pivot] >= digits[pivot + 1]) {
            pivot--;
        }
        if (pivot < 0) {
            return -1;
        }

        int successor = digits.length - 1;
        while (digits[successor] <= digits[pivot]) {
            successor--;
        }
        swap(digits, pivot, successor);
        reverse(digits, pivot + 1, digits.length - 1);

        long value = Long.parseLong(new String(digits));
        return value > Integer.MAX_VALUE ? -1 : (int) value;
    }

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

    private void swap(char[] digits, int i, int j) {
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
    }
}

import "strconv"

func nextGreaterElement(n int) int {
    digits := []byte(strconv.Itoa(n))

    pivot := len(digits) - 2
    for pivot >= 0 && digits[pivot] >= digits[pivot+1] {
        pivot--
    }
    if pivot < 0 {
        return -1
    }

    successor := len(digits) - 1
    for digits[successor] <= digits[pivot] {
        successor--
    }
    digits[pivot], digits[successor] = digits[successor], digits[pivot]
    for left, right := pivot+1, len(digits)-1; left < right; left, right = left+1, right-1 {
        digits[left], digits[right] = digits[right], digits[left]
    }

    value, _ := strconv.ParseInt(string(digits), 10, 64)
    if value > 1<<31-1 {
        return -1
    }
    return int(value)
}

复杂度分析

时间复杂度：$O(d)$，$d$ 为十进制数位数。寻找枢轴、寻找交换位置和反转后缀都只线性扫描数位。

空间复杂度：$O(d)$。字符数组和解析字符串占用线性空间；交换与反转本身是原地操作。

关键点总结

下一个排列的固定三步：找最右枢轴、交换最小的更大数位、反转后缀。

变动位置越靠右，高位保持得越多；枢轴增加得越少，结果越接近原数。

最长后缀已非递增，所以交换目标可从右侧找到，后缀也只需反转而无需排序。

数位重排后可能越过 int 上限，范围检查是本题相对「下一个排列」多出的关键约束。

易错点总结

寻找枢轴时用 > 而不是 >= 跳过相等数位，会在重复数字处错误停止。

从左向右找交换对象，可能选择过大的数位，结果不是最小的更大值。

交换后不反转后缀，得到的只是某个更大排列而非紧邻的下一个排列。

完全非递增时仍执行交换，会访问负下标；应在 pivot < 0 时立即返回。

直接用 32 位整数解析新排列，可能溢出；例如 1999999999 的下一排列超出上限。

把溢出判断写成 >= Integer.MAX_VALUE，会误拒绝恰好等于上限的合法结果。

相似题目

题目	难度	考察点
31. 下一个排列	中等	同一套三步定式的原始形态，作用于数组且要求原地修改无返回值
46. 全排列	中等	回溯生成全部排列，与逐个求后继形成两种截然不同的枚举方式
47. 全排列 II	中等	含重复元素的排列生成，需要靠排序加剪枝处理等值元素